Fire Containment in Planar Graphs

DOI10.1002/JGT.21673MaRDI QIDQ5325939zbMATH OpenOpenAlexFDO

Authors L. Esperet, Jan van den Heuvel, Frédéric Maffray, Félix Sipma

Publication date 31 July 2013

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

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

zbMATH Keywords

planar graphssurviving ratethe firefighter problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Abstract: In a graph $G$, a fire starts at some vertex. At every time step, firefighters can protect up to $k$ vertices, and then the fire spreads to all unprotected neighbours. The $k$-surviving rate $h{o}_k(G)$ of $G$ is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random. For a given class of graphs $cG$ we are interested in the minimum value $k$ such that $h{o}_k(G)geepsilon$ for some constant $epsilon>0$ and all $GincG$ i.e., such that linearly many vertices are expected to be saved in every graph from $cG$). In this note, we prove that for planar graphs this minimum value is at most 4, and that it is precisely 2 for triangle-free planar graphs.

Recommendations

• scientific article; zbMATH DE number 1802810
• Firefighting on geometric graphs with density bounds.
• Fighting constrained fires in graphs
• Firefighting on a random geometric graph
• Firefighting on trees and Cayley graphs
• The firefighter problem on graph classes
• Planar graph is on fire
• Fire containment in grids of dimension three and higher
• A matheuristic for the firefighter problem on graphs
• A graph theoretical approach to the firebreak locating problem

Cites work

• The firefighter problem for cubic graphs
• The firefighter problem for graphs of maximum degree three
• The Firefighter problem: a survey of results, directions and questions
• The surviving rate of a graph for the firefighter problem
• The surviving rate of an infected network

Cited in

(22)

• Planar graphs without chordal 5-cycles are 2-good
• 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 firefighter problem: empirical results on random graphs
• scientific article; zbMATH DE number 5016646 (Why is no real title available?)
• The 2-surviving rate of planar graphs without 6-cycles
• The surviving rate of digraphs
• The 2-surviving rate of planar graphs with average degree lower than \(\frac{9}{2}\)
• Planar graph is on fire
• An introduction to the discharging method via graph coloring
• A note on the surviving rate of 1-planar graphs
• Firefighting on trees and Cayley graphs
• Sparse graphs are not flammable
• Firefighting as a strategic game
• The surviving rate of NIC-planar graphs
• The surviving rate of planar graphs without short cycles
• The edge surviving rate of Halin graphs
• The 2-surviving rate of planar graphs without 4-cycles
• Advancing firefighter games: novel integer programming formulations and the cost-value model
• The surviving rate of planar graphs

This page was built for publication: Fire Containment in Planar Graphs

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