关于点传递图的彩虹连通数的研究

The rainbow connection number of a graph which is applied to measure the safety of a network was introduced and studied by Chartrand et al. in 2008. Since then the study of rainbow connection number has received considerable attention in the literature by many graph theorists, and now it becomes an active topic in graph theory. In 2011, it was shown by Chakraborty et al. that computing the rainbow connection number of an arbitrary graph is NP-Hard. Subsequently, there is a great interest towards determining or bounding the rainbow connection numbers of some special graph classes. In this project, we focus on the following two problems: investigate the rainbow connection numbers of vertex-transitive graphs, and study the related properties of the Cayley graph with given rainbow connection number. The main tools of this project are quotient graph theory, related theories of Cayley graphs and group theory.

2008年，以网络安全性度量为应用背景，Chartrand等人引入并研究了图彩虹连通数的概念。此后，彩虹连通数受到了国内外图论学者的广泛关注，现已成为图论研究中的一个热点。2011年，Chakraborty等人证明了计算图的彩虹连通数是NP-困难的。从而确定某些特殊图类的彩虹连通数或建立其彩虹连通数好的上下界是非常有意义的工作。本项目主要关注如下两个问题：其一，研究点传递图的彩虹连通数；其二，研究给定彩虹连通数的凯莱图的相关性质。本项目的主要研究工具是商图理论，凯莱图的相关理论以及群论。

Chartrand等人在2008年引入并研究了图彩虹连通数的概念。该方向现已成为图论研究中的一个热点。彩虹连通数除了作为一个组合概念之外，并且在网络安全上具有重要的应用背景。点传递图，特别是凯莱图，一直被当做对称互联网络的模型。鉴于彩虹连通数和点传递图的重要性，本项目主要研究了点传递图的彩虹连通数。研究结果如下：1.给出交换群上有向凯莱图的彩虹连通数的上界，利用我们的结论改进了李恒哲等人关于交换群上凯莱图的彩虹连通数的结果；给出交换群上双凯莱图的彩虹连通数的上界。2.决定了ladder图和Mobius ladder图的proper（顶点）k-连通数；决定了所有顶点数小于等于8的三度图的proper（顶点）k-连通数。该结果被国际SCI期刊《Utliltas Mathematica》接收待发表。3.研究了卡式积和字典积的广义3-连通度。该结果已在国际SCI期刊《Applied Mathematics and Computation》发表。