2026-08-21T18:34:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27399 2026-08-21T14:42:38Z ddc:004 open_access

Burning Graph Powers and Branching Trees Jansson, Jesper Kulamarva, Shashanka Murakami, Yukihiro Verhulst, Nikolaas Graph burning Burning number Graph power k^+-branching tree 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 in which all internal vertices have degree at least k+1. We then show that (k+1)^+-branching trees on n vertices have burning number at most ⌈√{4(k-1)n/k²}⌉. 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 alternative upper bound on the burning number of k^+-branching trees using the strongest currently known general burning number bound [Bastide et al.]. We then identify the ranges of k and n for which our bound outperforms or matches this alternative bound. Finally, we show that b(G^k) ≤ (1+o(1))√{n/k} based on the asymptotic burning number bound of Norin and Turcotte. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesper Jansson and Shashanka Kulamarva and Yukihiro Murakami and Nikolaas Verhulst 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.18 urn:nbn:de:0030-drops-273990 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode