Burning a graph as a model of social contagion
From MaRDI portal
(Redirected from Burning a graph as a model of social contagion)
Abstract: Graph burning is a model for the spread of social contagion. The burning number is a graph parameter associated with graph burning that measures the speed of the spread of contagion in a graph; the lower the burning number, the faster the contagion spreads. We prove that the corresponding graph decision problem is extbf{NP}-complete when restricted to acyclic graphs with maximum degree three, spider graphs and path-forests. We provide polynomial time algorithms for finding the burning number of spider graphs and path-forests if the number of arms and components, respectively, are fixed.
Recommendations
Cited in
(56)- Bounds on the burning number
- Burning number of graph products
- Burning graphs: a probabilistic perspective
- Burning numbers of path forests and spiders
- Improved bounds for burning fence graphs
- Burning numbers of \(t\)-unicyclic graphs
- Burnability of double spiders and path forests
- Burning graph classes
- Parameterized complexity of graph burning
- Burning the plane. Densities of the infinite Cartesian grid
- The generalized burning number of graphs
- Burning number of theta graphs
- Burning a graph is hard
- Burning two worlds
- Rumors spread slowly in a small-world spatial network
- A survey of graph burning
- Firefighting as a strategic game
- APX-hardness and approximation for the \(k\)-burning number problem
- APX-hardness and approximation for the \(k\)-burning number problem
- Selection of activators in finding the burning number
- Parameterized Complexity of Graph Burning
- Improved and generalized algorithms for burning a planar point set
- Burning and \(w\)-burning of geometric graphs
- Burn and win
- Improved pyrotechnics: closer to the burning number conjecture
- Burning Numbers of Barbells
- The burning number conjecture holds asymptotically
- Orientable burning number of graphs
- The burning number conjecture is true for trees without degree-2 vertices
- Farthest-first traversal for identifying multiple influential spreaders
- Adversarial graph burning densities
- Graph burning in community-based networks
- Burning number of Jahangir graphs
- Upper bounds and approximation results for the \(k\)-slow burning problem
- Burning sufficiently large p-caterpillars for a fixed p
- Algorithms for burning schedule reconfiguration problem on path forests
- Burning path-like and clique-like graphs
- Hypergraph burning, matchings, and zero forcing
- Homology of graph burnings
- Burn and win
- Information dissemination and confusion in signed networks
- Approximation algorithms for the graph burning on cactus and directed trees
- Orientable burning number of graphs
- Burning random trees
- On the burning number of generalized Petersen graphs
- Structural parameters for dense temporal graphs
- Throttling for the game of cops and robbers on graphs
- A row generation algorithm for finding optimal burning sequences of large graphs
- Between burning and cooling: liminal burning on graphs
- Extending graph burning to hypergraphs
- The k-radius of 2-connected graphs
- The generalized burning number of caterpillars
- On the burning number of the generalized Heawood graphs
- Deterministic approximation algorithm for graph burning
- Burning number of caterpillars
- Burning grids and intervals
This page was built for publication: Burning a graph as a model of social contagion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945268)
