一类稀疏图的边存活率

摘要：

目的:研究最小度为2且平均度有界的连通图的边存活率.方法:利用图染色理论中的经典方法权转移进行推导证明.结果:得到了如果G是一个有n个点m条边且最小度为2的连通图,满足(6/5-ε)n,其中0＜ε≤那么图G的边存活率ρ'(G)＞5ε/6-5ε.并由此推得如果G是一个最小度为2且围长至少为13的连通平面图,那么图G的边存活率ρ'(G)＞1/65.结论:若图G是一个最小度为2且平均度小于2.4的连通图,当火随机地在图G的任意两个相邻的顶点燃起时,1个消防员最多能保护的顶点数的平均值为正.

关键词：消防员问题、边存活率、稀疏图、围长

所属期刊栏目：31

分类号：O157.5(代数、数论、组合理论)

资助基金：国家自然科学基金项目No,11701541,11801512

在线出版日期：2021-02-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：400-404