Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909751348035584 |
|---|---|
| author | Tanaka, Hajime Tokushige, Norihide |
| author_facet | Tanaka, Hajime Tokushige, Norihide |
| contents | We give lower and upper bounds on the burning number of Hamming graphs, Johnson graphs, and halved cube graphs. For the lower bounds, we use the fact that $1$-skeletons of the eigenpolytopes of these graphs are isomorphic to the original graphs. Then, we present a dynamic search algorithm performed on the eigenpolytope to find an unburned vertex. This idea was originally used by Alon (Discrete Appl.\ Math.,\ 1992), who determined the burning number of the hypercube graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_17559 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes Tanaka, Hajime Tokushige, Norihide Combinatorics 05C85, 05C50, 90C10 We give lower and upper bounds on the burning number of Hamming graphs, Johnson graphs, and halved cube graphs. For the lower bounds, we use the fact that $1$-skeletons of the eigenpolytopes of these graphs are isomorphic to the original graphs. Then, we present a dynamic search algorithm performed on the eigenpolytope to find an unburned vertex. This idea was originally used by Alon (Discrete Appl.\ Math.,\ 1992), who determined the burning number of the hypercube graphs. |
| title | Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes |
| topic | Combinatorics 05C85, 05C50, 90C10 |
| url | https://arxiv.org/abs/2508.17559 |