基于消防员问题的网络存活率及相关参数研究

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11701541
项目类别：
青年科学基金项目
资助金额：
22.0万
负责人：
孔将旭
依托单位：
中国计量大学
学科分类：
A0409.图论及其应用
结题年份：
2020
批准年份：
2017
项目状态：
已结题
起止时间：
2018-01-01 至2020-12-31

项目参与者：
赵承业；陈琴；胡晓雪；李有浩；李红丽；
关键词：
图的存活率消防员问题色数平面图有向图

项目摘要

The spread of infections in the network poses great challenges to human being. It is an important issue in the network transmission control to protect individuals by finding effective intervention policies. Firefighter problem is a discrete dynamic model. The surviving rate of graphs is a new parameter to evaluate the whole defending ability of graphs. It is proved that almost all graphs have the k-surviving rate tends 0. Hence, it is significant to seek the graphs with the k-surviving rate is greater than a positive constant. In this project, we will combine the discharging method and planar separator theorem to study the surviving rate and some other parameters of graphs. (1)We try to solve or partly solve the Esperet’s conjecture, which says that plane graphs are 2-good and plane graphs with girth at least 5 are 1-good. And consider the k-optimal of plane graphs, aim to get the related threshold. (2)Also we will study more non-planar graphs, such as 1-planar graphs, IC-planar graphs and pseudo-outer planar graphs. (3) We investigate the surviving rate of digraphs and answer the question whether plane digraphs are 1-good. In addition, we will try to explore the relation between the surviving rate of graphs and oriented graphs. (4) We will study the surviving rate of graphs with more fires, specifically, the edge surviving rate of graphs. Moreover, we will explore the relation between the surviving rate and other parameters of graphs.

网络中的有害传播给人类带来巨大挑战，寻找有效的干预策略实现对网络传播的控制是一个重要的研究课题。消防员问题是一个离散动态干预传播模型，对应的存活率是刻画图的可靠性的一个全新参量。由于几乎所有图的k-存活率渐进趋于0，因此探寻存活率大于某个正常数的图类将有十分重要的理论意义和应用价值。本项目将结合权转移方法和平面分离定理来研究图的存活率及相关参数。主要考虑以下几个问题（1）研究平面图的存活率，力争解决或部分解决Esperet猜想，即：平面图是2-好的，围长至少为5的平面图是1-好的；考虑平面图k-优问题，争取得到相应的阈值。（2）研究1-平面图、IC-平面图、伪外平面图等非平面图类的存活率；（3）研究有向图的存活率，回答平面定向图是否是1-好的问题，以及探寻无向图与其定向图的存活率之间的关系；（4）研究图的多火源存活率，特别是图的边存活率。此外，我们也积极探索图的存活率与其他参数之间的联系。

结项摘要

本项目一方面研究消防员问题，主要围绕图的存活率及相关参数展开研究，如图的燃烧数；通过对图的结构性质研究，结合平面图分离定理和权转移方法，得到了Halin图，围长至少为13的平面图和不含5-圈平面图的边存活率的下界，推广了之前的结果；通过构造法和反证法，刻画了广义皮特森图的燃烧数；以及燃烧数达到紧的上下界的充分条件，改进了现有的结果。另一方面研究图的染色问题，如线性多彩染色、边-面染色、完备染色；我们研究了最大平均度有界和不含K4图子式图的线性多彩选择数，改进了之前关于多彩色数和线性色数的相关结果；进一步推进了Wang和Zhu提出完备染色猜想，即证明了最大度为7的平面图是完备10可染的；同时也证明了最大度为7的平面图是边面8-可染的；此外，还证明了若最大度至少为16的2-连通的简单平面图的边面色数等于其最大度，改进了Luo和Zhang之前的结果。三年内共发表（含接收）挂有基金号的学术论文11篇，其中SCI检索4篇，中国科学、数学年刊、数学进展各1篇。