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

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, and now it becomes an active topic in graph theory. As a natural generalization, Uchizawa et al. and Liu et al. independently presented the concept of total rainbow connection number of a graph. Although many results of the rainbow connection number (total rainbow connection number) were obtained in recent years, there are many important problems left to be resolved. In this project, we concentrate on the following four problems: Take advantage of the technique of the quotient graph, explore the total rainbow connection numbers of vertex-transitive graphs and edge-transitive graphs; Take advantage of Tutte’s 3-connected graph construction sequence, explore the total rainbow connection numbers of 3-connected graphs; Start with algorithm, explore the computational complexity of the total rainbow connection numbers of vertex-transitive graphs and edge-transitive graphs; Take advantage of related theories of Cayley graphs and group theory, explore the related properties of the Cayley graph with given total rainbow connection number. This project hopefully enriches the results of total rainbow connection, and provides some theoretical basis for network security.

2008年，以网络安全性度量为应用背景，Chartrand等人引入并研究了图的彩虹连通数。此后，彩虹连通数受到了国内外图论学者的广泛关注，现已成为图论研究中的一个热点。作为一个自然地推广，Uchizawa等人和Liu等人独立的提出了图的全彩虹连通数的概念。近年来，关于彩虹连通数（全彩虹连通数）的研究工作已取得了丰富的结果，但仍有众多重要问题亟待解决。本项目重点关注如下四个问题：其一，借用商图技巧，探索点传递图和边传递图的全彩虹连通数的上界；其二，利用Tutte 3-连通图构造序列，探索3-连通图的全彩虹连通数；其三，从算法角度入手，探索点传递图和边传递图的全彩虹连通数的算法复杂性；其四，利用凯莱图的相关理论以及群论知识，探索给定全彩虹连通数的凯莱图的相关性质。本项目有望丰富全彩虹连通性的结论，为网络安全方面提供一定的理论基础。

以网络安全性度量为应用背景，Chartrand等人2008年引入并研究了图的彩虹连通数，彩虹顶点连通数和全彩虹连通数是彩虹连通数的自然推广。此后，彩虹连通数及其相关推广课题已成为图论研究中的一个热点。本项目主要研究了特殊图的全彩虹连通数和彩虹顶点连通数。除此之外，在有向图的正常连通数和全正常连通数、顶点彩虹指标、广义连通度等方面也取得了若干结果。主要研究结果如下：1.研究了直径为2的外平面图的全彩虹连通数，改进了Huang等人关于外平面图的彩虹连通数的结果；修改了Liu等人论文中的错误，并决定了完全图和圈的thorn graph的全彩虹连通数。2.研究了circular ladders和Mobius ladders的全彩虹2-连通数，确定了所有点数为8或更少的3度正则图的全彩虹2-连通数。3.研究了几类图运算的彩虹顶点连通数，并证明了对于一个图G的线图L(G)，rvc(L(G))≤rc(G)成立。4.为unicyclic图和补图的3-顶点彩虹指标提供了紧的上界。5.决定了路的双定向、圈的双定向、完全多部图的双定向、圈图、循环有向图和仙人掌有向图的(强)正常连通数和(强)全正常连通数。6.决定了递归循环图的广义3-点连通度和广义3-边连通度，研究了线图的广义k-点连通度。