Source-linked AI summary
How to burn a graph
Anthony Bonato, Jeannette Janssen, Elham Roshanbin
TL;DR
The paper asks how to model and quantify the speed of contagion spreading through a network. It introduces the burning number and studies its properties, reporting characterizations and bounds, computations for several graph classes, and results for the Iterated Local Transitivity model.
Problem
The paper asks how to quantify the speed of contagion spreading through a graph and which nodes to target, and in what order, to reach the network quickly.
Source: §1 · p. 1Method
The authors define a deterministic graph-burning process and study its burning number through characterizations, bounds, and computations on graph classes.
Source: §1 · pp. 1–2Results
The paper gives a tree-decomposition characterization and bounds, proves Nordhaus-Gaddum-type results, and determines burning numbers in the Iterated Local Transitivity model.
Source: §5 · p. 15Takeaways & Limitations
The burning number measures how rapidly social contagion spreads in a graph, with lower values indicating faster spread.
Source: §5 · p. 15Burning numbers remain undetermined for many graph classes, including trees and disconnected graphs, and for real-world social networks such as Facebook or LinkedIn.
Source: §5 · p. 15
Abstract
from arXiv · showhide
We introduce a new graph parameter called the burning number, inspired by contact processes on graphs such as graph bootstrap percolation, and graph searching paradigms such as Firefighter. The burning number measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We provide a number of properties of the burning number, including characterizations and bounds. The burning number is computed for several graph classes, and is derived for the graphs generated by the Iterated Local Transitivity model for social networks.
1. Introduction
The paper models contagion spreading through a network as a deterministic graph process, asking which nodes to target and when to minimize the time to reach the whole network. It introduces the burning number and outlines characterizations, bounds, and computations for selected graph classes.
1. Introduction
- Each round burns one unburned node, then spreads fire from previously burned nodes to their unburned neighbours; b(G) is the minimum rounds needed to burn the whole graph.The process is presented as a simplified, deterministic model of contagion spread.Source: §1 · p. 1
- A burning sequence lists the nodes ignited in each round, and an optimal sequence is a shortest one; lower burning numbers correspond to easier contagion spread.For P4, (v2, v4) is an optimal burning sequence.Source: §1 · pp. 1–2
- The paper introduces the burning number, gives a tree-decomposition characterization and bounds, and computes it for the Iterated Local Transitivity model.Computing the burning number is NP-complete even for trees.Source: §1 · p. 2
2. Properties of the burning number
The burning number has a rooted-tree-partition characterization, and the paper derives consequences for spanning trees, subgraphs, paths, and graph coverings. It also relates burning to distance domination and conjectures a square-root upper bound for connected graphs.
Covering bounds
- A cover by t connected subgraphs of radius at most k gives b(G) ≤ t + k; a radius-constrained cover with at most k sets gives b(G) ≤ k.These bounds use connected subgraphs with controlled radius to cover all nodes.Source: §2 · p. 3
Characterizations
- Burning a graph in k steps is equivalent to partitioning its nodes into k rooted trees with descending height limits and pairwise root-distance constraints.The heights are at most k − 1 through 0, and roots of trees i and j must be at distance at least |i − j|.Source: §2 · p. 4
Spanning trees
- b(G) equals the minimum burning number over all spanning subtrees of G, reducing computation on a graph to its spanning trees.The proof combines the tree partition characterization with the fact that adding edges cannot increase the burning number.Source: §2 · p. 5
Subgraph monotonicity
- For trees, every subtree H satisfies b(H) ≤ b(T); for general graphs this monotonicity is established for isometric subtrees, but can fail for non-isometric ones.A path of order 5 with a universal node added has burning number 2, versus 3 for the path.Source: §2 · pp. 6–7
Graph classes
- For a path Pn and cycle Cn, the burning number is ⌈n^1/2⌉; any graph of order n with a Hamiltonian path has burning number at most ⌈n^1/2⌉.The paper also states that the general lower and upper bounds are attained by paths and spider graphs SP(s, r), respectively, where s ≥ r.Source: §2 · pp. 7–8
Domination and conjecture
- If b(G) = k, then k ≥ γ_{k−1}(G); the paper conjectures that every connected graph of order n has b(G) ≤ ⌈n^1/2⌉.Here γ_{k−1}(G) is the minimum size of a (k − 1)-distance dominating set.Source: §2 · pp. 8–9
3. Nordhaus-Gaddum Type Results
The section develops sum and product bounds for the burning numbers of a graph and its complement, in the style of Nordhaus–Gaddum results. It also gives bounds for connected complementary pairs and proposes a sharper product conjecture.
3. Nordhaus-Gaddum Type Results
- The sum bound is sharp for complete graphs, strict for cycles, and its lower bound is attained by K2 and star graphs.For Kn the sum is n+2; for Cn it is ⌈n^1/2⌉+3 < n+2.Source: §3 · p. 10
- For graphs of order n≥6, b(G)b( G) ≤2n, with equality for complete graphs.Source: §3 · p. 11
- For connected complementary graphs of order n≥6, the sum is at most 3⌈n^1/2⌉−1 and the product is at most n+6.Source: §3 · pp. 11–12
- The authors conjecture that connected complementary graphs of order n have burning-number product at most n+4.Source: §3 · p. 12
4. Burning in the ILT Model
In the Iterated Local Transitivity (ILT) model, each new generation clones every existing node, adding an independent set of nodes. Despite exponential growth in graph order, the burning number stays at its initial value or increases by one, according to a condition on the last source in an optimal burning sequence.
4. Burning in the ILT Model
- The ILT model repeatedly adds clones of each node, joined to that node and all its neighbors; the new nodes form an independent set.The model starts from any fixed finite connected graph G0.Source: §4 · p. 12
- Although ILT graphs grow exponentially in order with t, their burning number remains constant or rises by at most one.The exact outcome depends on the initial graph’s optimal burning sequences, as characterized by Theorem 23.Source: §4 · p. 12
- For every t ≥ 1, b(Gt) is either b(G0) or b(G0) + 1; it remains b(G0) exactly when every optimal burning sequence of G0 has a neighbor of its last source burned at stage k − 1.Otherwise, b(Gt) = b(G0) + 1.Source: §4 · pp. 12, 14, 15
- For a path Pn with ⌈√n⌉ = k, the ILT burning number is k + 1 when n = k², and k when n ≠ k².The distinction follows from whether an optimal burning sequence leaves a neighbor of its last source unburned at stage k − 1.Source: §4 · p. 15
5. Conclusions and future work
The paper introduces the burning number, characterizes it, gives bounds, and determines it for graphs in the ILT model. It leaves broad questions open, including a conjectured bound for connected graphs and computation on real-world social networks.
5. Conclusions and future work
- The paper introduces b(G), characterizes it through tree decompositions, gives bounds, and determines it for the ILT model.The bounds support computation for a variety of graphs and are also used for distance-domination and Nordhaus–Gaddum-type results.Source: §5 · p. 15
- For a connected graph G of order n, the authors conjecture b(G) ≤ ⌈√n⌉; determining b(G) remains open for many classes, including trees and disconnected graphs.Source: §5 · p. 15
- The burning number remains unstudied on real-world social networks such as Facebook or LinkedIn.The authors suggest that online social networks may have burning number of constant order as they grow, based on Theorem 23.Source: §5 · p. 15
- The authors identify threshold-based burning, where a node burns only after at least r > 1 neighbors burn, as future work that may produce complex dynamics.Source: §5 · p. 16