Burning Graph Powers and Branching Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915970081095680 |
|---|---|
| author | Jansson, Jesper Kulamarva, Shashanka Murakami, Yukihiro Verhulst, Nikolaas |
| author_facet | Jansson, Jesper Kulamarva, Shashanka Murakami, Yukihiro Verhulst, Nikolaas |
| contents | Graph burning is a discrete-time process that models the spread of social contagion. Initially, all vertices are unburned. In each round, one unburned vertex is selected and burned, while any unburned vertex that has a burned neighbour from the previous round also becomes burned. The burning number of a graph is the minimum number of rounds needed to burn the entire graph. In this paper, we study the burning number of graph powers. First, we show that for a connected graph $G$, its graph power $G^k$ contains a $(k+1)^+$-branching tree as a spanning tree. A $(k+1)^+$-branching tree is one whose internal vertices have degree at least $k+1$. We then show that $(k+1)^+$-branching trees on $n$ vertices have burning number at most $\left\lceil{\sqrt{\frac{4(k-1)n}{k^2}}}~\right\rceil$. As the burning number of a graph is at most the burning number of any of its spanning trees, this gives an upper bound on the burning number of graph powers. We also derive an explicit bound building on the results of Bastide et al., and identify the ranges of $k$ and $n$ for which our bound outperforms theirs. Finally, we show that $b(G^k) \le (1+o(1))\sqrt{n/k}$ based on the asymptotic burning number bound of Norin and Turcotte. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23004 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Burning Graph Powers and Branching Trees Jansson, Jesper Kulamarva, Shashanka Murakami, Yukihiro Verhulst, Nikolaas Combinatorics Discrete Mathematics Graph burning is a discrete-time process that models the spread of social contagion. Initially, all vertices are unburned. In each round, one unburned vertex is selected and burned, while any unburned vertex that has a burned neighbour from the previous round also becomes burned. The burning number of a graph is the minimum number of rounds needed to burn the entire graph. In this paper, we study the burning number of graph powers. First, we show that for a connected graph $G$, its graph power $G^k$ contains a $(k+1)^+$-branching tree as a spanning tree. A $(k+1)^+$-branching tree is one whose internal vertices have degree at least $k+1$. We then show that $(k+1)^+$-branching trees on $n$ vertices have burning number at most $\left\lceil{\sqrt{\frac{4(k-1)n}{k^2}}}~\right\rceil$. As the burning number of a graph is at most the burning number of any of its spanning trees, this gives an upper bound on the burning number of graph powers. We also derive an explicit bound building on the results of Bastide et al., and identify the ranges of $k$ and $n$ for which our bound outperforms theirs. Finally, we show that $b(G^k) \le (1+o(1))\sqrt{n/k}$ based on the asymptotic burning number bound of Norin and Turcotte. |
| title | Burning Graph Powers and Branching Trees |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2604.23004 |