The surviving rate of planar graphs
type: Item
instance of: scholarly article
title: The surviving rate of planar graphs
zbMATH Open document ID: 1239.05042
author: Jiangxu Kong
author: Xuding Zhu
author: Weifan Wang
published in: Theoretical Computer Science
publication date: 2012-03-13T00:00:00Z
review text: This paper considers firefighting on graphs. Given a graph \(G\) suppose that a fire breaks out at vertex \(v\). At each step the firefighters can protect \(k\) vertices, after which the fire spreads to any unprotected vertex adjacent to a vertex already on fire. The firefighters' goal is to maximize the number of saved vertices, that is, the number of vertices remaining unburned after the fire no longer spreads. Let \(sn_k(v)\) be the maximum number of vertices in \(G\) that can be saved when a fire breaks out at \(v \in V(G)\). The \(k\)-surviving rate of \(G\) is \(\rho_k(G) = \sum_{v \in V(G)} sn_k(G)/n^2\). This represents the average proportion of saved vertices over all possible starting vertices. The authors focus on the \(4\)-surviving rate of planar graphs. Let \(\delta\) denote the minimum degree of \(G\). They show \(\rho_4 (G) > 1/9\) for \(\delta \leq 3\), \(\rho_4 (G) > 3/19\) for \(\delta = 4\), and \(\rho_4(G) > 3/11\) for \(\delta = 5\). It follows that \(\rho_4(G)\) is bounded away from 0 for any planar \(G\). The proof uses discharging techniques based on Euler's formula to find suitable small configurations.
reviewed by: Dan S. Archdeacon
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6014309
zbMATH Keywords: firefighting
zbMATH Keywords: surviving rate
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.10.002
OpenAlex ID: W2033212080
cites work: The Surviving Rate of a Graph for the Firefighter Problem
cites work: Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem
cites work: The firefighter problem for graphs of maximum degree three
cites work: Q3614015
cites work: The firefighter problem for cubic graphs
cites work: Q4457546
cites work: Allee effect and control of lake system invasion
cites work: The surviving rate of an infected network
cites work: Q3147255
cites work: The surviving rate of an outerplanar graph for the firefighter problem
DOI: 10.1016/J.TCS.2011.10.002
description: scientific article; zbMATH DE number 6014309