Planar graph is on fire

DOI10.1016/J.TCS.2015.06.002zbMATH Open1331.05152arXiv1311.1158OpenAlexW1609723440MaRDI QIDQ501009FDOQ501009

Authors: Przemysław Gordinowicz 

Publication date: 8 October 2015

Published in: Theoretical Computer Science (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 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.

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

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

zbMATH Keywords

planar graphfirefighter problemsurviving rate

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (10)

• 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
• Planar graphs without chordal 5-cycles are 2-good
• Fire Containment in Planar Graphs
• How to Burn a Graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• A note on the surviving rate of 1-planar graphs
• Title not available (Why is that?)

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)