The 2-surviving rate of planar graphs without 5-cycles

被引:1
作者
Tingting Wu
Jiangxu Kong
Weifan Wang
机构
[1] Zhejiang Normal University,Department of Mathematics
[2] Xiamen University,School of Mathematical Science
来源
Journal of Combinatorial Optimization | 2016年 / 31卷
关键词
Firefighter problem; Surviving rate; Cycle; Planar graph;
D O I
暂无
中图分类号
学科分类号
摘要
Let G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} be a connected graph with n≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 2$$\end{document} vertices. Let k≥1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 1$$\end{document} be an integer. Suppose that a fire breaks out at a vertex v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document} of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document}. A firefighter starts to protect vertices. At each step, the firefighter protects k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-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 snk(v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {sn}_k(v)$$\end{document} denote the maximum number of vertices in G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} that the firefighter can save when a fire breaks out at vertex v\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v$$\end{document}. The k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-surviving rate ρk(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho _k(G)$$\end{document} of G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is defined to be 1n2∑v∈V(G)snk(v)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{n^2}\sum _{v\in V(G)} {\hbox {sn}}_{k}(v)$$\end{document}, which is the average proportion of saved vertices. In this paper, we prove that if G\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G$$\end{document} is a planar graph with n≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 2$$\end{document} vertices and without 5-cycles, then ρ2(G)>1363\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\rho _2(G)>\frac{1}{363}$$\end{document}.
引用
收藏
页码:1479 / 1492
页数:13
相关论文
共 47 条
[1]  
Bazgan C(2013)The firefighter problem with more than one firefighter on trees Discrete Appl Math 161 899-908
[2]  
Chopin M(2009)The surviving rate of a graph for the firefighter problem SIAM J Discrete Math 23 1814-1826
[3]  
Ries B(2010)Surviving rates of graphs with bounded treewidth for the firefighter problem SIAM J Discrete Math 24 1322-1335
[4]  
Cai L(2013)More fires and more fighters Discrete Appl Math 161 2410-2419
[5]  
Wang W(2013)Fire containment in planar graphs J Graph Theory 73 267-279
[6]  
Cai L(2009)The firefighter problem: a survey of results, directions and questions Australas J Comb 43 57-77
[7]  
Cheng Y(2007)The firefighter problem for graphs of maximum degree three Discrete Math 307 2094-2105
[8]  
Verbin E(2010)The firefighter problem for cubic graphs Discrete Math 310 614-621
[9]  
Zhou Y(2012)The surviving rate of planar graphs Theoret Comput Sci 416 65-70
[10]  
Costa V(2014)Structural properties and surviving rate of planar graphs Discrete Math Algorithm Appl 6 1450052-189