Planar graph is on fire

DOI10.1016/J.TCS.2015.06.002MaRDI QIDQ501009zbMATH OpenOpenAlexFDO

Authors Przemysław Gordinowicz

Publication date 8 October 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

firefighter problemplanar graphsurviving rate

Mathematics Subject Classification ID

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

Abstract: Let $G$ be any connected graph on $n$ vertices, $nge2.$ Let $k$ be any positive integer. Suppose that a fire breaks out on some vertex of $G.$ Then in each turn $k$ firefighters can protect vertices of $G$ --- each can protect one vertex not yet on fire; Next a fire spreads to all unprotected neighbours. The emph{$k$-surviving} rate of G, denoted by $h{o}_k(G),$ is the expected fraction of vertices that can be saved from the fire by $k$ firefighters, provided that the starting vertex is chosen uniformly at random. In this paper, it is shown that for any planar graph $G$ we have $h{o}_3(G)gefrac221.$ Moreover, 3 firefighters are needed for the first step only; after that it is enough to have 2 firefighters per each round. This result significantly improves known solutions to a problem of Cai and Wang (there was no positive bound known for surviving rate of general planar graph with only 3 firefighters). The proof is done using the separator theorem for planar graphs.

Recommendations

• Fire Containment in Planar Graphs
• The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)
• Structural properties and surviving rate of planar graphs
• The edge surviving rate of a class of planar graphs for the firefighter problem
• The surviving rate of planar graphs

Cites work

• A Separator Theorem for Planar Graphs
• Fire Containment in Planar Graphs
• Graphs with average degree smaller than \(\frac{30}{11}\) burn slowly
• Sparse graphs are not flammable
• The 2-surviving rate of planar graphs without 4-cycles
• The Firefighter problem: a survey of results, directions and questions
• The surviving rate of a graph for the firefighter problem
• The surviving rate of planar graphs
• Towards more efficient infection and fire fighting

Cited in

(17)

• Planar graphs without chordal 5-cycles are 2-good
• A lower bound of the surviving rate of a planar graph with girth at least seven
• Plane graphs of diameter two are 2-optimal
• Surviving rate of graphs and firefighter problem
• The 2-surviving rate of planar graphs without 5-cycles
• Structural properties and surviving rate of planar graphs
• The edge surviving rate of a class of planar graphs for the firefighter problem
• scientific article; zbMATH DE number 5016646 (Why is no real title available?)
• The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)
• A note on the surviving rate of 1-planar graphs
• Fire Containment in Planar Graphs
• How to Burn a Graph
• The surviving rate of NIC-planar graphs
• The surviving rate of planar graphs without short cycles
• The edge surviving rate of Halin graphs
• Maximizing vertex rescue: investigating the firefighter problem with edge subdivision
• Advancing firefighter games: novel integer programming formulations and the cost-value model

This page was built for publication: Planar graph is on fire

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