有向图的彩虹连通问题的研究

Rainbow coloring is a new branch of edge coloring. It has an important application in the transmission of information and network security. It has been concerned by Tuza, Chartrand and other famous scholars. Now it is currently one of a hot topic in graph theory..In this project, we will study on the bounded and the computational complexity of the rainbow connective number of digraphs. We will study the relationship between the rainbow connective number and other invariants (such as minimum degree, connective degree and radius, etc.) in digraphs, and give the bounds of the rainbow connective number by using the invariants of digraphs. Finally, we consider the rainbow connectivity problem from the point of view of complexity, and use polynomial resolution method to determine the complexity of the rainbow connective number of digraphs.

彩虹染色是一个新的染色分支，在信息传递和网络安全中有着重要的应用，受到了Tuza、Chartrand等著名学者的关注和研究，是目前图论研究的热点问题之一。.本项目旨在研究某些特殊无向图和有向图的彩虹连通数的界和算法复杂性问题。从分析强有向图的结构入手，研究彩虹连通数与其它的不变量（如：最小度、连通度和半径等）之间的关系，争取利用图的不变量给出有向图彩虹连通数的界；从复杂性的角度考虑有向图的彩虹连通问题，运用多项式归结方法来确定有向图彩虹连通的难易程度。

彩虹染色是一个新的染色分支，在信息传递和网络安全中有着重要的应用，受到了Tuza、Chartrand等著名学者的关注和研究，是目前图论研究的热点问题之一。本项目旨在研究某些特殊无向图和有向图的彩虹连通数的界和算法复杂性问题。从分析强有向图的结构入手，研究彩虹连通数与其它的不变量（如：最小度、连通度和半径等）之间的关系，争取利用图的不变量给出有向图彩虹连通数的界；从复杂性的角度考虑有向图的彩虹连通问题，运用多项式归结方法来确定有向图彩虹连通的难易程度。. 本项目在国家自然科学基金的资助下，经项目组成员的一致努力，取得了一定的研究成果。完成论文四篇，其中被接收SCI论文三篇，专著章节一篇；课题组申请到国家自然科学基金青年基金一项和山东省自然科学基金青年基金一项。一方面，项目组成员得到了学术上的锻炼与提高，增强了独立进行科学研究的能历；另一方面，项目组负责人的学术能力得到了进一步的提 升，项目组成员多人次在国内学术会议上作学术报告。