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

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

项目编号： No.11501223

项目类型： 青年科学基金项目

立项/批准年度： 2016

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

项目作者： 陈莉莉

作者单位： 华侨大学

项目金额： 18万元

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

中文关键词： 图染色；彩虹连通数；算法复杂性；极小彩虹连通图

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

英文关键词： graph coloring;rainbow connection number;algorithmic complexity;minimal rainbow connected graph