错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Burning Hamming graphs

  • Norihide Tokushige

摘要

The Hamming graph H(nq) is defined on the vertex set \([q]^n\) [ q ] n and two vertices are adjacent if and only if they differ in precisely one coordinate. Alon (Disc Appl Math 37(38):9–11, 1992) proved that the burning number of H(n, 2) is \(\lceil \frac{n}{2}\rceil +1\) n 2 + 1 . In this note we give a short proof of a fact that the burning number of H(nq) is \((1-\frac{1}{q})n+O(\sqrt{n\log n})\) ( 1 - 1 q ) n + O ( n log n ) for fixed \(q\ge 2\) q 2 and \(n\rightarrow \infty \) n .