pith. sign in

arxiv: 2604.23004 · v1 · submitted 2026-04-24 · 🧮 math.CO · cs.DM

Burning Graph Powers and Branching Trees

Jesper Jansson , Shashanka Kulamarva , Yukihiro Murakami , Nikolaas Verhulst This is my paper

Pith reviewed 2026-05-08 10:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords graph burningburning numbergraph powersspanning treesbranching treescontagion processdistance graphs
0
0 comments X

The pith

The kth power of any connected n-vertex graph has burning number at most (1+o(1))sqrt(n/k).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the kth power of a connected graph G always contains a spanning tree in which every internal vertex has degree at least k+1. It then shows that any n-vertex tree with this property can be burned in at most the ceiling of the square root of 4(k-1)n over k squared steps. Because the burning number of a graph is never larger than the burning number of a spanning tree, the same upper bound holds for the entire graph power. The authors also obtain the asymptotic form b(G^k) at most (1+o(1)) times the square root of n/k by combining their construction with a known general bound on burning numbers. This gives a concrete way to estimate how many steps are needed for a contagion process to cover graphs in which two vertices are adjacent whenever their distance in the original graph is at most k.

Core claim

For every connected graph G, the power G^k contains a (k+1)^+-branching tree as a spanning tree. Every (k+1)^+-branching tree on n vertices has burning number at most ceil of the square root of 4(k-1)n over k squared. Therefore the burning number of G^k is at most this quantity. The paper further derives b(G^k) <= (1+o(1))sqrt(n/k) from the asymptotic burning-number bound of Norin and Turcotte and compares the new explicit bound against earlier work of Bastide et al. for ranges of k and n.

What carries the argument

The (k+1)^+-branching tree: a tree whose internal vertices all have degree at least k+1; it functions as a spanning tree of G^k whose burning number supplies an upper bound on the burning number of the full power graph.

If this is right

  • b(G^k) is at most ceil(sqrt(4(k-1)n/k^2)) for any connected G.
  • The new bound improves on the explicit bound derived from Bastide et al. inside certain ranges of k and n.
  • b(G^k) is at most (1+o(1))sqrt(n/k) for large n.
  • Burning numbers of distance-k graphs can be controlled by the existence of high-minimum-degree branching spanning trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the bound is close to tight, then raising the power index k reduces the number of steps needed for contagion to spread roughly like the square root of 1/k.
  • The same spanning-tree construction may help bound other spreading or search parameters, such as the cop number or the length of the longest path, inside powered graphs.
  • The result can be tested directly by computing exact burning numbers of G^k for small connected graphs such as paths, cycles, or grids and checking the gap to the stated upper bound.

Load-bearing premise

Every connected graph's kth power must contain a spanning tree whose internal vertices have degree at least k+1, and the burning number of any graph must be at most the burning number of any of its spanning trees.

What would settle it

A single connected graph G on n vertices together with an integer k for which either G^k has no spanning tree with all internal degrees at least k+1, or the burning number of G^k exceeds ceil of sqrt(4(k-1)n/k^2).

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that every connected graph G admits a (k+1)^+-branching spanning tree in its k-th power G^k. It then establishes that any (k+1)^+-branching tree on n vertices has burning number at most ⌈√(4(k-1)n/k²)⌉. Combined with the standard inequality b(H) ≤ b(T) for any spanning tree T of H, this yields b(G^k) ≤ ⌈√(4(k-1)n/k²)⌉. The paper also derives an explicit bound from the results of Bastide et al., identifies parameter ranges where the new bound is superior, and proves the asymptotic b(G^k) ≤ (1+o(1))√(n/k) via the Norin-Turcotte bound on paths.

Significance. If the proofs are correct, the work supplies a concrete, constructive upper bound on the burning number of graph powers that is competitive with prior results and asymptotically tight up to the (1+o(1)) factor, matching the order achieved by caterpillar graphs. The explicit comparison with Bastide et al. and the use of known tight path-burning bounds on the worst-case branching-tree structure are useful for applications in contagion modeling on networks with increased connectivity.

minor comments (3)
  1. The abstract states that an explicit bound is derived from Bastide et al. but does not display the formula; adding the closed-form expression would improve readability.
  2. The definition of a (k+1)^+-branching tree (internal vertices have degree at least k+1) appears only after the main claim; restating it in the introduction or as a numbered definition would aid readers.
  3. A small concrete example (e.g., a cycle or path power for small k) showing the constructed spanning tree and its burning sequence would help illustrate the central construction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No specific major comments were provided in the report, so we have no point-by-point rebuttals to address. We will incorporate any minor suggestions during the revision process.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper proves existence of a (k+1)^+-branching spanning tree in G^k (for connected G) via an explicit construction, derives the burning-number bound for such trees on n vertices by direct calculation from the tree structure, and invokes the standard external fact b(H) <= b(T) for any spanning tree T. The asymptotic (1+o(1))sqrt(n/k) is obtained by applying a known result of Norin and Turcotte to the same worst-case trees. No equation reduces to a fitted parameter renamed as prediction, no self-citation is load-bearing for the central claim, and no ansatz or uniqueness theorem is smuggled in from prior author work. The chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the standard definition of graph burning, the fact that burning number is monotone under taking spanning trees, and the usual axioms of graph theory; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption The burning number of any graph is at most the burning number of any of its spanning trees.
    Invoked to transfer the tree bound to G^k.
  • standard math Standard definitions of graph powers, branching trees, and the burning process.
    Background definitions from the field.

pith-pipeline@v0.9.0 · 5580 in / 1449 out tokens · 26054 ms · 2026-05-08T10:53:32.208669+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

7 extracted references · 7 canonical work pages

  1. [1]

    2 Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, Théo Pierron, and Mikaël Rabie

    doi:10.1016/0166-218X(92)90121-P. 2 Paul Bastide, Marthe Bonamy, Anthony Bonato, Pierre Charbit, Shahin Kamali, Théo Pierron, and Mikaël Rabie. Improved pyrotechnics: closer to the burning number conjecture.Electron. J. Comb., 30(4): Article P4.2, 2023.doi:10.37236/11113. 3 Stéphane Bessy, Anthony Bonato, Jeannette C. M. Janssen, Dieter Rautenbach, and El...

    work page doi:10.1016/0166-218x(92)90121-p 2023

  2. [2]

    4 Anthony Bonato

    doi: 10.1016/j.dam.2017.09.012. 4 Anthony Bonato. A survey of graph burning.Contrib. Discrete Math., 16(1):185–197,

    work page doi:10.1016/j.dam.2017.09.012 2017

  3. [3]

    5 Anthony Bonato, Jeannette Janssen, and Elham Roshanbin

    doi:10.55016/ojs/cdm.v16i1.71194. 5 Anthony Bonato, Jeannette Janssen, and Elham Roshanbin. How to burn a graph.Internet Mathematics, 12(1-2):85–100, 2016.doi:10.1080/15427951.2015.1103339. 6 Anthony Bonato and Thomas Lidbetter. Bounds on the burning numbers of spiders and path-forests.Theor. Comput. Sci., 794:12–19,

    work page doi:10.55016/ojs/cdm.v16i1.71194 2016

  4. [4]

    7 Stephen Finbow and Gary MacGillivray

    Special Issue on Theory and Applications of Graph Searching.doi:10.1016/j.tcs.2018.05.035. 7 Stephen Finbow and Gary MacGillivray. The firefighter problem: A survey of results, directions and questions.Australas. J. Comb., 43:57–77,

    work page doi:10.1016/j.tcs.2018.05.035 2018

  5. [5]

    Refinements of degree conditions for the existence of a spanning tree without small degree stems.Discrete Math., 348(2): Article 114307, 2025.doi:10.1016/j.disc.2024.114307

    8 Michitaka Furuya, Akira Saito, and Shoichi Tsuchiya. Refinements of degree conditions for the existence of a spanning tree without small degree stems.Discrete Math., 348(2): Article 114307, 2025.doi:10.1016/j.disc.2024.114307. 9 S. Louis Hakimi. Optimum locations of switching centers and the absolute centers and medians of a graph.Oper. Res., 12(3):450–...

    work page doi:10.1016/j.disc.2024.114307 2025

  6. [6]

    doi: 10.1007/978-3-030-63072-0_12. J. Jansson, S. Kulamarva, Y. Murakami, and N. Verhulst 23:13 11 Max R. Land and Linyuan Lu. An upper bound on the burning number of graphs. InWorkshop on Algorithms and Models for the Web-Graph, W A W 2016, volume 10088 ofLecture Notes in Computer Science, pages 1–8. Springer, Cham, 2016.doi:10.1007/978-3-319-49787-7_1. ...

    work page doi:10.1007/978-3-030-63072-0_12 2016

  7. [7]

    15 Sergey Norin and Jérémie Turcotte

    Preprint, arXiv:2509.03144 [math.CO].doi:10.48550/arXiv.2509.03144. 15 Sergey Norin and Jérémie Turcotte. The burning number conjecture holds asymptotically.J. Comb. Theory Ser. B, 168:208–235, 2024.doi:10.1016/j.jctb.2024.05.003. CVIT 2016

    work page doi:10.48550/arxiv.2509.03144 2024