Burning rooted graph products
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917300512227328 |
|---|---|
| author | Peca-Medlin, John |
| author_facet | Peca-Medlin, John |
| contents | The burning number $b(G)$ of a graph $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$ vertices can be burned in at most $\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_00304 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Burning rooted graph products Peca-Medlin, John Combinatorics Data Structures and Algorithms Probability The burning number $b(G)$ of a graph $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$ vertices can be burned in at most $\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. |
| title | Burning rooted graph products |
| topic | Combinatorics Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2603.00304 |