The 2-surviving rate of planar graphs with average degree lower than 92

DOI10.1002/JGT.22254zbMATH Open1402.05046arXiv1608.01488OpenAlexW2504148289WikidataQ129899496 ScholiaQ129899496MaRDI QIDQ4646940FDOQ4646940

Authors: Przemysław Gordinowicz 

Publication date: 3 January 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: Let $G$ be any connected graph on $n$ vertices, $nge2.$ Let $k$ be any positive integer. Suppose that a fire breaks out at some vertex of $G.$ Then, in each turn firefighters can protect at most $k$ vertices of $G$ not yet on fire; Next the fire spreads to all unprotected neighbours. The $k$-surviving rate of G, denoted by $h{o}_k(G),$ is the expected fraction of vertices that can be saved from the fire, provided that the starting vertex is chosen uniformly at random. In this note, it is shown that for any planar graph $G$ with average degree $4frac12-epsilon,$ where $epsilonin(0,1],$ we have $h{o}_2(G)gefrac29epsilon$. In particular, the result implies a significant improvement of the bound for 2-surviving rate for triangle-free planar graphs (Esperet, van den Heuvel, Maffray and Sipma, 2013) and for planar graphs without 4-cycles (Kong, Wang, Zhang, 2012). The proof is done using the separator theorem for planar graphs. This paper is the corrected version of (Gordinowicz, 2018) unified with the corrigendum.

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

Recommendations

• The 2-surviving rate of planar graphs without 5-cycles
• Planar graph is on fire
• The 2-surviving rate of planar graphs without 4-cycles
• The surviving rate of planar graphs
• Fire Containment in Planar Graphs

zbMATH Keywords

planar graphfirefighter problemsurviving rate

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Games on graphs (graph-theoretic aspects) (05C57)

Cited In (10)

• Surviving rate of graphs and firefighter problem
• The 2-surviving rate of planar graphs without 5-cycles
• The 2-surviving rate of planar graphs without 6-cycles
• Planar graph is on fire
• The 2-surviving rate of planar graphs without 4-cycles
• The surviving rate of planar graphs
• Erratum: The 2‐surviving rate of planar graphs with average degree lower than 92
• Title not available (Why is that?)
• Sparse graphs are not flammable
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly

This page was built for publication: The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)

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