How to burn a graph

2015/07/23 by Anthony Bonato, Bonato, Anthony, Jeannette Janssen +3 · 7 citations
Physics and Astronomy · Computer Science · #Complex Network Analysis Techniques #Peer-to-Peer Network Technologies #Opinion Dynamics and Social Influence

paper · pdf · doi:10.48550/arxiv.1507.06524

Abstract

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.

Cited by

• Graph burning: an overview of mathematical programs
• Burning games on strong path products
• Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
• The burning number conjecture holds for trees of order n with at most \lfloor √(n-1)\rfloor degree-2 vertices
• Zero Forcing on Iterated Graph Models
• Burning a Graph is Hard
• Between burning and cooling: liminal burning on graphs

Related

• A survey of graph burning
• Approximation Algorithms for Graph Burning
• New heuristics for burning graphs
• How to cool a graph
• Burning a Graph is Hard