Planar graph is on fire

• Published in 2015
• Added on 2015-12-02

Let $G$ be any connected graph on $n$ vertices, $n \ge 2.$ 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 $\rho_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 $\rho_3(G) \ge \frac{2}{21}.$ 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.

Links

• http://arxiv.org/abs/1311.1158
• http://arxiv.org/pdf/1311.1158v2

Other information

BibTeX entry

@article{Gordinowicz2015,
	key = {Gordinowicz2015},
	type = {article},
	title = {Planar graph is on fire},
	author = {Gordinowicz, Przemys{\l}aw},
	abstract = {Let {\$}G{\$} be any connected graph on {\$}n{\$} vertices, {\$}n \ge 2.{\$} 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 {\$}\rho{\_}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 {\$}\rho{\_}3(G) \ge \frac{\{}2{\}}{\{}21{\}}.{\$} 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.},
	comment = {},
	date_added = {2015-12-02},
	date_published = {2015-08-01},
	urls = {http://arxiv.org/abs/1311.1158,http://arxiv.org/pdf/1311.1158v2},
	collections = {Attention-grabbing titles,Puzzles,Fun maths facts},
	issn = 03043975,
	journal = {Theoretical Computer Science},
	month = {aug},
	pages = {160--164},
	url = {http://arxiv.org/abs/1311.1158 http://arxiv.org/pdf/1311.1158v2},
	volume = 593,
	year = 2015,
	archivePrefix = {arXiv},
	eprint = {1311.1158},
	primaryClass = {math.CO},
	urldate = {2015-12-02}
}