图的彩虹连通性和单色连通性

Connectivity is one of the most fundamental subjects in graph theory. The rainbow connection and monochromatic connection of graphs are two interesting ways to strengthen the concept of classical connectivity. And they have wide applications in information transfer and network security. So the topic has attracted the attention of many scholars in the field of graph theory, such as Benny Sudakov, Michael Krivelevich, Alan Frieze, Yair Caro and so on. Although the study of rainbow connection and monochromatic connection has already yielded a series of nice results, there still remain some important problems which are worth working on..In this research project, we attempt to study the rainbow connection and monochromatic connection from the points of graph theory, algorithm and algebra, and mainly focus on the following three questions: First, show the computational complexity of rainbow index and monochromatic connection number; Second, establish the algebraic representation of rainbow index and monochromatic connection number, and try to apply the methods in computer algebra to solve the original problems; Third, discuss the open problem of determining the monochromatic connection number of graphs with diameter two by their structure properties as well as computer experiments. We believe that the project will give us a deeper insight into the rainbow connection and monochromatic connection of graphs.

连通性是图论中最重要的概念之一。图的彩虹连通性和单色连通性不仅是对经典连通性的加强，而且在信息传输与网络安全等方面有着广泛的应用。因此，这一课题吸引了许多图论学者的关注，如 B. Sudakov， M. Krivelevich，A. Frieze，Y. Caro等。虽然彩虹连通性和单色连通性的研究已经取得了一些优美的结果，但目前仍有很多重要的问题有待解决。.本项目将围绕图的彩虹连通性和单色连通性，从算法复杂性、代数表示、结构分析多个角度展开研究，重点讨论以下三个问题：一、证明彩虹指数与单色连通数的计算复杂性；二、确立彩虹指数与单色连通数的代数表示，并尝试使用代数中的计算方法给出原问题的求解；三、从图的结构特征出发，加以计算机辅助，探讨“直径为2的图的单色连通数”这一公开问题。本项目的研究将帮助我们对图的彩虹连通性和单色连通性产生更深刻更全面的认识。

三年来，本项目在国家自然科学基金的资助下，对图的彩虹连通性和单色连通性展开研究，顺利完成了预期的主要目标。发表学术论文6篇，其中5篇为SCI检索期刊论文，1篇为EI检索会议论文。本项目取得的主要研究成果如下：(1) 在图的彩虹连通性方面，对于一般的二部图，计算其彩虹连通数已被证明是一个NP-困难问题。对于完全二部图这类特殊的二部图，我们利用编码理论，完全确定了其彩虹2-连通数的值，部分回答了Fujita等学者提出的公开问题；此外，线图也是一类非常重要的图类。我们研究了线图的3-彩虹指数，通过细致的结构分析，给出了好的上下界。(2) 在图的单色连通性方面，我们提出了图的单色顶点连通数这一概念，确定了其与最小度、直径、生成树叶子数等图参数之间的关系，并完全解决了单色顶点连通数的Erdos–Gallai型和Nordhaus-Gaddum型问题，建立了单色连通性与图论经典理论之间的联系。(3) 由于控制集是研究彩虹连通性的常用工具，我们也对控制集展开了研究，给出了全控制集和双罗马控制集这两类重要控制集的多个线性规划模型，并进行了数值实验，验证了算法的运行效率。(4) 我们还研究了赋权图的顶点距离之和问题，以及特定子图禁忌的染色临界图的个数问题。这些结果发表在Applied Mathematics and Computation，Discrete Applied Mathematics，Journal of Combinatorial Optimization等杂志上。