Sparse graphs are not flammable

DOI10.1137/120876113MaRDI QIDQ5408614zbMATH OpenOpenAlexFDO

Authors Paweł Prałat

Publication date 10 April 2014

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.0723

zbMATH Keywords

firefighterrandom regular graphssurviving rate

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this paper, we consider the following emph{$k$-many firefighter problem} on a finite graph $G=(V,E)$. Suppose that a fire breaks out at a given vertex $vinV$. In each subsequent time unit, a firefighter protects $k$ vertices which are not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate $ho(G)$ of $G$ is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of $G$. Let $a{u}_k=k+2-frac1k+2$. We show that for any $epsilon>0$ and $kge2$, each graph $G$ on $n$ vertices with at most $(a{u}_k-epsilon)n$ edges is not flammable; that is, $ho(G)>frac2epsilon5a{u}_k>0$. Moreover, a construction of a family of flammable random graphs is proposed to show that the constant $a{u}_k$ cannot be improved.

Recommendations

• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• The surviving rate of a graph for the firefighter problem
• Fighting constrained fires in graphs
• The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)
• Fire Containment in Planar Graphs

Cited in

(14)

• Planar graphs without chordal 5-cycles are 2-good
• Burning graphs: a probabilistic perspective
• Surviving rate of graphs and firefighter problem
• Asymptotic surviving rate of trees with multiple fire sources
• The 2-surviving rate of planar graphs without 5-cycles
• Fighting constrained fires in graphs
• Firefighting on square, hexagonal, and triangular grids
• Planar graph is on fire
• The spread of fire on a random multigraph
• Firefighting on a random geometric graph
• The surviving rate of NIC-planar graphs
• The surviving rate of planar graphs without short cycles
• The edge surviving rate of Halin graphs
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly

This page was built for publication: Sparse graphs are not flammable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5408614)