×

zbMATH — the first resource for mathematics

Planar graphs without chordal 5-cycles are 2-good. (English) Zbl 1393.05094
Summary: Let \(G\) be a connected graph with \(n\geq 2\) vertices. Suppose that a fire breaks out at a vertex \(v\) of \(G\). A firefighter starts to protect vertices. At each step, the firefighter protects two vertices not yet on fire. At the end of each step, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let \(\mathrm{sn}_2(v)\) denote the maximum number of vertices in \(G\) that the firefighter can save when a fire breaks out at vertex \(v\). The 2-surviving rate \(\rho_2(G)\) of \(G\) is defined to be the real number \(\frac{1}{n^2} \sum_{v\in V(G)} \mathrm{sn}_2(v)\). Then it is obvious that \(0<\rho_2(G)<1\). The graph \(G\) is called 2-good if there is a constant \(c>0\) such that \(\rho_2(G)>c\). In this paper, we prove that every planar graph with \(n\geq 2\) vertices and without chordal 5-cycles is 2-good.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bazgan, C; Chopin, M; Ries, B, The firefighter problem with more than one firefighter on trees, Discrete Appl Math, 161, 899-908, (2013) · Zbl 1263.05068
[2] Cai, L; Wang, W, The surviving rate of a graph for the firefighter problem, SIAM J Discrete Math, 23, 1814-1826, (2009) · Zbl 1207.05098
[3] Cai, L; Cheng, Y; Verbin, E; Zhou, Y, Surviving rates of graphs with bounded treewidth for the firefighter problem, SIAM J Discrete Math, 24, 1322-1335, (2010) · Zbl 1221.05210
[4] Costa, V; Dantas, S; Dourado, MC; Penso, L; Rautenbach, D, More fires and more fighters, Discrete Appl Math, 161, 2410-2419, (2013) · Zbl 1285.05121
[5] Esperet, L; Heuvel, J; Maffray, F; Sipma, F, Fire containment in planar graphs, J Graph Theory, 73, 267-279, (2013) · Zbl 1269.05026
[6] Finbow, S; MacGillivray, G, The firefighter problem: a survey of results, directions and questions, Australas J Comb, 43, 57-77, (2009) · Zbl 1179.05112
[7] Finbow, S; King, A; MacGillivray, G; Rizzi, R, The firefighter problem for graphs of maximum degree three, Discrete Math, 307, 2094-2105, (2007) · Zbl 1120.68081
[8] Gordinowicz, P, Planar graph is on fire, Theor Comput Sci, 593, 160-164, (2015) · Zbl 1331.05152
[9] Jin, J; Wei, Y, A note on 3-choosability of plane graphs under distance restrictions, Discrete Math Algorithms Appl, 9, 1750011, (2017) · Zbl 1358.05079
[10] Karst, N; Langowitz, J; Oehrlein, J; Troxell, DS, Radio k-chromatic number of cycles for large \(k\), Discrete Math Algorithms Appl, 9, 1750031, (2017) · Zbl 1373.05162
[11] King, A; MacGillivray, G, The firefighter problem for cubic graphs, Discrete Math, 310, 614-621, (2010) · Zbl 1216.05107
[12] Kong, J; Wang, W; Zhu, X, The surviving rate of planar graphs, Theor Comput Sci, 416, 65-70, (2012) · Zbl 1239.05042
[13] Kong, J; Zhang, L; Wang, W, Structural properties and surviving rate of planar graphs, Discrete Math Algorithms Appl, 6, 1450052, (2014) · Zbl 1303.05039
[14] Lipton, RJ; Tarjan, RE, A separate theorem for planar graphs, SIAM J Appl Math, 36, 177-189, (1979) · Zbl 0432.05022
[15] Prałat, P, Sparse graphs are not flammable, SIAM J Discrete Math, 27, 2157-2166, (2014) · Zbl 1285.05124
[16] Sudev, NK; Chithra, KP; Satheesh, S; Kok, J, On certain parameters of equitable coloring of graphs, Discrete Math Algorithms Appl, 9, 1750054, (2017) · Zbl 1373.05070
[17] Vasanthi, R; Subramanian, K, On the minimum vertex coloring transversal dominating sets in graphs and their classifications, Discrete Math Algorithms Appl, 9, 1750069, (2017) · Zbl 1386.05144
[18] Wang, W; Finbow, S; Wang, P, The surviving rate of an infected network, Theor Comput Sci, 411, 3651-3660, (2010) · Zbl 1207.68072
[19] Wang, W; Kong, J; Zhang, L, The 2-surviving rate of planar graphs without 4-cycles, Theor Comput Sci, 457, 158-165, (2012) · Zbl 1251.05042
[20] Wang, W; Finbow, S; Wang, P, A lower bound of the surviving rate of a planar graph with girth at least seven, J Comb Optim, 27, 621-642, (2014) · Zbl 1291.90288
[21] Wang, W; Finbow, S; Kong, J, The 2-surviving rate of planar graphs without 6-cycles, Theor Comput Sci, 518, 22-31, (2014) · Zbl 1370.05152
[22] Wu, T; Kong, J; Wang, W, The 2-surviving rate of planar graphs without 5-cycles, J Comb Optim, 31, 1479-1492, (2016) · Zbl 1369.90182
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.