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

项目名称： 有向图的彩虹连通问题的研究

项目编号： No.11626148

项目类型： 专项基金项目

立项/批准年度： 2016

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

项目作者： 岳军

作者单位： 山东师范大学

项目金额： 3万元

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

中文关键词： 边染色；彩虹染色；有向图；近似算法；概率方法

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

英文关键词： edge coloring；rainbow coloring；digraphs；approximation algorithm；probabilistic method