Burning rooted graph products
John Peca-Medlin · 2026
Read Burning rooted graph products by John Peca-Medlin (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00304.txt.
Introduction
Peca-Medlin studies the burning number: rounds needed to burn every vertex as fires spread and one new fire starts each step. The Burning Number Conjecture claims every n-vertex graph burns within the square root of n rounds, rounded up. The author investigates rooted graph products, focusing on combs: a path spine with a tooth at each vertex. Rooted products force communication through designated roots, modelling hub-and-spoke designs. Peca-Medlin proves the conjecture for all comb graphs and pins down their burning number's order in every regime.
Catalog record
| CREATOR | John Peca-Medlin |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 78473 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.00304
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Burning rooted graph products John Peca-Medlin Abstract The burning number b ( G ) b(G) of a graph G G is the minimum number of rounds required to burn all vertices when, at each discrete step, existing fires spread to neighboring vertices and one new fire may be ignited at an unburned vertex. This parameter measures the speed of influence propagation in a network and has been studied as a model for information diffusion and resource allocation in distributed systems. A central open problem, the Burning Number Conjecture (BNC), asserts that every graph on n n vertices can be burned in at most ⌈ n ⌉ \lceil\sqrt{n}\rceil rounds, a bound known to be sharp for paths and verified for several structured families of trees. We investigate rooted graph products, focusing on comb graphs obtained by attaching a path (a “tooth”) to each vertex of a path (the “spine”). Unlike classical symmetric graph products, rooted products introduce hierarchical bottlenecks: communication between local subnetworks must pass through designated root vertices, providing a natural model for hub-and-spoke or chain-of-command architectures. We prove that the BNC holds for all comb graphs and determine the precise asymptotic order of their burning number in every parameter regime, including exact formulas in the spine-dominant case that generalize the known formula for paths. Our approach is constructive, based on an explicit greedy algorithm that is optimal or near-optimal depending on the regime. 1 Introduction The burning process is a discrete-time process on a graph G . At time t=0 , all vertices are unburned. At each subsequent time step t+1 , every existing fire spreads fire to all of its neighbors, while in addition a new fire is started at a single unburned vertex, if available. The burning number of G , denoted b(G) , is the minimum number of steps required to burn all vertices of G . An equivalent characterization is in terms of sphere packing on a graph. Let d(u,v) denote the usual graph distance, and for v\in V(G) and r\geq 0 , let B(v,r)=\{u\in V(G):d(u,v)\leq r\} . Then b(G)=\min\left\{k:\exists v_{1},\ldots,v_{k}\in V(G)\text{ such that }V(G)=\bigcup_{i=1}^{k}B(v_{i},k-i)\right\}. Here B(v_{i},k-i) consists precisely of the vertices that can be burned by the fire started at time i by time k . Establishing the burning number for a graph is NP-complete, including also for trees and other simple families of graphs [ BBJ+17 ] . That said, several basic graph families admit explicit formulas. For the path P_{n} with n vertices, one has b(P_{n})=\lceil\sqrt{n}\rceil. To see this: since |B(v,r)\cap P_{n}|\leq 2r+1 , then using k balls of radii k-1,k-2,\dots,0 covers at most \sum_{i=1}^{k}(2(k-i)+1)=\sum_{i=0}^{k-1}(2i+1)=k^{2} vertices. So k^{2}\geq n is necessary and sufficient. See Figure 1 for an optimal burning sequence of P_{16} . 1 2 3 4 Figure 1 : Optimal burning sequence using 4 fires for P_{16} . At the opposite extreme, for the complete graph K_{n} with n\geq 2 , one has B(v,1)=V(K_{n}) for any vertex v , and hence b(K_{n})=2 . For perfect binary trees with n=2^{h}-1 vertices and height h=\log_{2}(n+1) , the optimal strategy is to ignite the root and allow the fire to propagate, yielding b(T)=h+1=\Theta(\log n) . Optimality is established by showing any other burning sequence cannot burn enough leaves in a shorter time span (see [ DIMP23 ] ). A central open problem in the area is the Burning Number Conjecture (BNC), introduced in [ BJR16 ] . Conjecture 1 (BNC) . If G is a connected graph on n vertices, then b(G)\leq\lceil\sqrt{n}\rceil. In essence, the conjecture asserts that the path is extremal among connected graphs. The conjecture has been verified for several graph classes, including paths, cycles, Hamiltonian graphs [ BJR16 ] , caterpillars [ LHH20 , HKT20 ] , spiders [ BL19 , DDS+18 ] , and trees without degree-two vertices [ Mur24 ] . General progress toward the conjecture has led to increasingly sharp upper bounds (e.g., [ LL16 , BBJ+18 ] ). The furthest (nonasymptotic) advancement is due to Bastide et al. [ BBB+23 ] , who proved b(G)\leq\left\lceil\sqrt{\frac{4}{3}n}\right\rceil+1. Asymptotically, Norin and Turcotte [ NT24 ] have resolved the BNC, showing that b(G)\leq(1+o(1))\sqrt{n}. Beyond extremal bounds, burning numbers have also been studied for random graph models. For Erdős–Rényi graphs G(n,p) with sufficiently large p=p_{n} , the burning number is O(1) with high probability [ MPR17 ] . For critical Galton–Watson trees conditioned to have n vertices with finite variance offspring distribution, it has been shown that b(G)=\Theta(n^{1/3}) with high probability [ DEP25 ] . Other recent directions include burning growing graphs and lattices [ BGNP26 ] , as well as randomly burning graphs [ BC25 ] . Graph products provide a natural framework for constructing larger networks from simpler components. Mitsche, Prałat, and Paweł [ MPR18 ] studied burning numbers of symmetric graph products and proved that for connected graphs G and H , \max\{b(G),b(H)\}\leq b(G\boxtimes H)\leq b(G\,\square\,H)\leq\min\{b(G)+\mathrm{rad}(H),\,b(H)+\mathrm{rad}(G)\}, (1) where G\boxtimes H denotes the strong product, G\,\square\,H the Cartesian product, and \operatorname{rad}(G) denotes the radius of a graph G , \mathrm{rad}(G)=\min_{v\in V(G)}\operatorname{ecc}(v) , where the eccentricity of a vertex v is \operatorname{ecc}(v)=\max_{u\in V(G)}d(u,v) . These symmetric products model diffusion in relatively homogeneous networks: propagation occurs along multiple independent directions, reflecting grid-like communication structures in which no single vertex plays a central routing role. Similarly, the lexicographic product (also studied in [ MPR18 , BEKM21 ] ) introduces dense inter-layer connectivity, enabling rapid cross-layer dissemination once adjacency in the base graph is established. In all these cases, communication is symmetric or highly interconnected, and no structural bottlenecks significantly constrain the spread of information. The rooted product captures a fundamentally different architecture. Given graphs G and H with a distinguished root vertex r\in V(H) , the rooted product G\circ H is obtained by taking one copy of G and, for each vertex v\in V(G) , attaching a copy of H by identifying v with the root r of that copy. Each vertex of G therefore serves as a gateway to a local copy of H . In G\circ H , every copy of H connects to the remainder of the graph through a single vertex, creating unavoidable communication bottlenecks and producing a hierarchical network consisting of a backbone (the graph G ) together with local subnetworks (copies of H ). Inter-branch communication must pass through designated gateway vertices, in contrast to the parallel diffusion present in strong or Cartesian products. Rooted products thus provide a natural deterministic model for constrained hierarchical systems, such as chains of command or hub-and-spoke networks, where dissemination is mediated through structured control nodes. In this paper, we study the burning number of rooted products of paths. 1.1 Main results The first contribution is for general rooted graph products. We establish an immediate relationship of the rooted graph product back to the Cartesian product of graphs: Theorem 1 . Let G be a graph and H a rooted graph with root r_{H}\in V(H) . Then b(G\,\square\,H)\leq b(G\circ H)\leq b(G)+\operatorname{ecc}(r_{H}). This result is direct enough, we include a proof here. Proof. Since G\circ H is an isometric subgraph in G\,\square\,H , then b(G\,\square\,H)\leq b(G\circ H) (see [ BJR16 ] ). We can define a burning sequence on G\circ H by first using a minimal burning sequence with b(G)