关于彩虹连通数和传统图参数关系的研究

The rainbow connection number of a graph which is applied to measure the safety of a network is introduced by Chartrand et al. in 2008. It is hard to determine the rainbow connection number of a graph, for example, given a graph, deciding if the rainbow connection number of it equals 2 is NP-Complete. Under the consideration of the practical application and the complexity of the rainbow connection number, in recent years, many graph theorists have concerned about and investigated the rainbow connection number of graphs, and proposed a lot of problems on the rainbow connection number. In this project, we shall explore the bounds of the rainbow connection number on several classic graph parameters, and rainbow-coloring algorithms.. . There exists close relation between the rainbow connection number and some classic graph parameters, so the method of studying the rainbow connection number is flexible. We shall explore the relation between the rainbow connection number and minimum degree, connectivity and diameter, etc. by traditional tools, such as, graph theory, algebra and probability theory..

2008年，以网络安全性度量为应用背景，Chartrand等学者提出了图彩虹连通数的概念。确定一个图的彩虹连通数是困难的，比如，确定一个图彩虹连通数是否等于2是NP-完全的。由于彩虹连通数具有实际应用价值及其研究困难性，近几年，许多图论学家一直关注和研究图的彩虹连通数，并提出诸多备受关注的问题。本项目将在若干传统图参数限制下，探索彩虹连通数的界以及相关多项式染色算法。.. 彩虹连通数和传统图参数存在着密切关系，因此该领域的研究方法较为灵活。我们将运用诸多传统的图参数研究工具——图论、代数及概率方法等,来探索彩虹连通数和最小度、连通度和直径等传统图参数的联系。

2008年，以网络安全性度量为应用背景，Chartrand等学者提出了图彩虹连通数的概念。确定一个图的彩虹连通数是困难的，比如，确定一个图彩虹连通数是否等于2是NP-完全的。由于彩虹连通数具有实际应用价值及其研究困难性，近几年，许多图论学家一直关注和研究图的彩虹连通数，并提出诸多备受关注的问题。. 在本项目中，（a）我们得到了图的并、添加边、删除边和同时添加边和点等图操作的彩虹连通数的紧的上下界；（b）我们获得了Cartesian图和字典积图的彩虹点连通数的紧的上下界；（c）我们建立了彩虹连通数和点彩虹连通数的第一个非平凡的不等式关系。. 此外，依托本项目，我们也做了一些不在项目计划中的工作，例如，2-（边）连通控制数与控制数（或独立数）的关系、斯坦纳树填装数和树连通度等。