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

项目名称： 关于彩虹连通数和传统图参数关系的研究

项目编号： No.11401181

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

立项/批准年度： 2014

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

项目作者： 李恒哲

作者单位： 河南师范大学

项目金额： 23万元

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

中文关键词： 彩虹连通数；彩虹点连通数；图操作；控制数；斯坦纳树填装数

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

英文关键词： Rainbow connection number；Rainbow vertex connection number；Graph operation；Domination number；Steiner tree packing number