彩虹连通数的算法复杂性和极图问题的若干研究

The concept of rainbow connection number was introduced by Chartrand et al. in 2008. It is a strengthening of the classical connectivity, and plays an important role in the transmission of information and network security. Chakraborty et al. showed that determining the rainbow connection number of a graph is NP-hard. Thus, the study of the upper bounds and approximate algorithms of rainbow connection number is meaningful, and it attracts many experts to study this topic, such as Caro, Tuza, Frieze. Although many results of the rainbow connection number were obtained, there are many problems left to be resolved, this topic will still be one of the hot issues.. In this project, we will focus on the following three aspects of the rainbow connection number of graphs: 1. We will start from the special graphs, and study the algorithmic complexity of determining the rainbow connection number of special graphs. 2. We will study from the algorithm point of view, and give the effective approximate algorithms for the rainbow connection number of graphs. 3. We will study the properties of minimal rainbow connected graphs with the method of extremal graph theory, and try to characterize the structure of minimal rainbow connected graphs.

彩虹连通数的概念是由Chartrand等学者于2008年提出来的，它是经典连通度的加强，在信息传输和网络安全中有非常重要的作用。Chakraborty等学者证明确定一般图的彩虹连通数是NP-困难的，因此从上界、近似算法等角度研究图的彩虹连通数是非常有意义的，也吸引了许多国内外图论专家的关注和研究，如Caro，Tuza，Frieze等。虽然彩虹连通数的研究取得了丰富的结果，但还有众多重要问题亟待解决，这一课题仍将是图论学者研究的热点问题之一。. 本项目主要从以下三个方面研究图的彩虹连通数：1. 从特殊图入手，考虑特殊图的彩虹连通数的算法复杂性；2. 从算法角度考虑一般图，探索求解一般图的彩虹连通数的好的近似算法；3. 借鉴极值图论中极图的刻画方法，研究极小彩虹连通图的性质，并探索其结构特点，力争给出其结构刻画。

图染色问题是图论研究的热点问题之一，具有重要的理论价值和实际意义。彩虹连通数是经典连通度的加强，在信息传输和网络安全中有非常重要的作用。强边染色和DP-染色分别是经典边染色和列表染色的推广，在实际生活中也有广泛应用。因此对这些图染色的研究是非常有意义的。. 本项目在国家自然科学基金委的资助及项目成员的共同努力下，完成了项目的主要目标，但在研究内容上略有调整。目前，项目组得到的主要结果有：. （1）我们研究了广义 Petersen 图P(n,k)的结构，给出P(n,1)的彩虹（顶点）连通数的精确值以及P(n,1)，P(n,2)，P(n,3)的[1,2]-控制数；. （2）我们解决了李莎莎等关于广义连通度的算法复杂性的一个猜想，同时给出一个求广义边连通度的多项式时间算法；. （3）我们研究了围长较大的平面图及边权较小的图的强边色数的界；给出了DP-4-可染图的两个充分条件。