Graph Burning On Large $p$-Caterpillars
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913615925215232 |
|---|---|
| author | Cox, Danielle Messinger, M. E. Ojakian, Kerry |
| author_facet | Cox, Danielle Messinger, M. E. Ojakian, Kerry |
| contents | Graph burning models the spread of information or contagion in a graph. At each time step, two events occur: neighbours of already burned vertices become burned, and a new vertex is chosen to be burned. The big conjecture is known as the {\it burning number conjecture}: for any connected graph on $n$ vertices, all $n$ vertices can be burned after at most $\lceil \sqrt{n}\ \rceil$ time steps. It is well-known that to prove the conjecture, it suffices to prove it for trees. We prove the conjecture for sufficiently large $p$-caterpillars. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_12970 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Burning On Large $p$-Caterpillars Cox, Danielle Messinger, M. E. Ojakian, Kerry Combinatorics 05C57 Graph burning models the spread of information or contagion in a graph. At each time step, two events occur: neighbours of already burned vertices become burned, and a new vertex is chosen to be burned. The big conjecture is known as the {\it burning number conjecture}: for any connected graph on $n$ vertices, all $n$ vertices can be burned after at most $\lceil \sqrt{n}\ \rceil$ time steps. It is well-known that to prove the conjecture, it suffices to prove it for trees. We prove the conjecture for sufficiently large $p$-caterpillars. |
| title | Graph Burning On Large $p$-Caterpillars |
| topic | Combinatorics 05C57 |
| url | https://arxiv.org/abs/2412.12970 |