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

项目名称： 关于点传递图的彩虹连通数的研究

项目编号： No.11526082

项目类型： 专项基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 马迎宾

作者单位： 河南师范大学

项目金额： 3万元

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

中文关键词： 彩虹连通数；proper k-连通数；广义连通度；凯莱图；

英文摘要： 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.

英文关键词： rainbow connection number；proper k-connection number；generalized connectivity；Cayley graph；