图的彩虹着色若干问题的研究

As a new type of graph coloring, rainbow coloring has a widely application in network management and security, and is currently a hotspot in the field of graph theory. The graph parameters of rainbow coloring include rainbow connection number, strong rainbow connection number, rainbow k-connection number and rainbow vertex-connection number. Cayley graph is not only one of the most important research topics in algebraic graph theory, but also a network model which is widely studied in computer science. The main contents of our project include: (1) The difference of rainbow connection number and strong rainbow connection number, we will estimate their difference in terms of some graph parameters and give the structural condition provided that they are equal;(2) We will discuss the structure of the graph with large (strong) rainbow connection number, and determine the sufficient conditions and necessary conditions, respectively;(3) We will investigate the above four parameters of Cayley graphs and their subclasses. In this project, we try to promote the research on the topics of rainbow coloring and Cayley graph. This project belongs to the interdisciplinary research in graph theory and computer science because of the relationship betwwen rainbow coloring and network management and security.

彩虹着色作为一种新的着色问题，研究涉及包括彩虹连通数、强彩虹连通数、彩虹k-连通数、彩虹点连通数在内的许多图参数，在网络管理和安全等方面有着广泛的应用，是目前图论研究的热点问题之一。凯莱图常被用作互联网络模型，对其的研究是代数图论的重要内容。项目内容包括：（1）研究强彩虹连通数与彩虹连通数的差值问题，用若干图参数对其差值进行估计并给出使得这两个彩虹着色参数相等的图结构条件；（2）研究（强）彩虹连通数取值较大时的图的结构问题，分别给出（强）彩虹连通数取值较大时的充分条件和必要条件；（3）研究凯莱图及其子类的彩虹着色问题，对凯莱图及其子类的彩虹连通数等彩虹着色参数进行定界或给出精确值。项目的实施将进一步完善彩虹着色理论，拓展凯莱图的相关研究，并将彩虹着色研究与网络应用领域相联系，属于图论与计算机科学的交叉性研究。

彩虹着色作为一种新的着色问题，研究涉及包括彩虹连通数、强彩虹连通数、彩虹k-连通数、彩虹点连通数在内的许多图参数。广义连通度，包括广义k-连通度、k-连通度等，是经典连通度概念的推广。彩虹着色与广义连通度均在网络安全方面有着广泛应用背景，是当前图论研究的热点问题。.负责人与其他成员主要研究了彩虹着色问题与广义联通度两类问题，另外还研究了其它相关的图论问题。具体来讲包括以下内容：（1）研究了彩虹着色问题与广义连通度相关的差值问题。对彩虹着色问题几类参数的差值以及几类广义连通度之间的差值进行定界。（2）研究了彩虹着色问题与广义连通度的定界问题。包括对一般图的彩虹着色参数、几类广义连通度进行定界；对特殊图类的上述参数计算精确值；研究乘积图的彩虹着色参数与广义连通度问题。（3）研究了彩虹着色问题与广义连通度相关的极值问题；研究在彩虹着色参数与广义连通度参数取值较大时图的结构刻画问题。.项目的研究进展和主要成果如下：（1）本项目用图的内点数与边数给出一般图的全彩虹连通数的一个紧上界，并给出了该上界达到的充分必要条件。（2）本项目给出了全彩虹连通数的Nordhaus-Gaddum型紧下界。（3）得到了卡氏积图彩虹指数的一个紧上界。（4）刻画了全彩虹连通数取值较大时图的结构，找出了极值图。（5）对这三种广义连通度进行比较并定界。（6）本项目研究得出几类乘积图的广义边连通度的紧界，以及几类特殊乘积图类的广义连通度的精确值。（7）得到若干特殊图类(如凯莱图)的广义连通度的精确值。（8）研究了几类广义连通度的极值问题，刻画具有较大广义k-（边）连通度的图；对给定k-(边)连通度的图的最少边数进行定界，并求出一些特殊情形下的精确值。.项目资助期间，项目负责人及课题组成员积极开展学术交流，与同行开展合作研究，在学术期刊上共发表论文16篇，超额完成了项目预期目标。这些成果进一步完善和发展了彩虹着色理论与广义连通度理论。