图的正常连通性的极值和复杂性问题的研究

In light of the September 11, 2001, terrorist attacks, an abundance of network security issues arose and immediately came to the forefront of mathematical research. Inspired by rainbow connection and network security reliability, Andrews et al. and Borozan et al. introduced the concept of properly colored connectivity of graphs. It is not only an interesting way to strengthen the classical connectivity requirement in a graph, but also has very important applications in transportation and telecommunication, social science, large-scale integrated circuit design and so on. This project will focus on the extremal problems and computational complexity of proper connection number of graphs. The following topics are included: (1) Determine the undirected extremal graphs for all proper k-connection numbers; (2) Classify the directed graphs with directed proper connection number 2; (3) Computing the complexity of proper conection number of graphs. Through this project, it is planned to provide new methods and ideas for the study of properly colored connectivity of graphs and make breakthrough progress.

2001年9月11日美国恐怖袭击事件后，政府机构之间的网络通信安全出现了重大问题，因此如何加强各部门之间网络通信安全的可靠性立即成为了数学科学研究的前沿。受彩虹连通性和网络安全可靠性的启发，Andrews等人和Borozan等人在2012年相互独立地提出了图的正常连通性的概念。它不仅可以看作是一般图连通性的加强形式，而且在交通与通讯，社会科学、大规模集成电路设计等方面有及其重要的应用，因此对其开展研究工作有着重要的理论意义和应用价值。本项目围绕图的正常连通数的极值问题和算法复杂性问题开展研究，主要研究内容如下：一，无向图中正常k-连通数的极值刻画问题；二，有向图中正常连通数为2的极图问题；三，图的正常连通数的算法复杂性问题，这方面的研究结果较少，内容也较新颖。计划通过本项目的研究，为图的正常连通性研究提供新方法和新思路，并取得突破性进展。

图的连通性和染色理论是图论学科的两个主要研究分支，受到了广大学者们的关注。图的彩虹连通性、正常连通性、树连通性、路连通性以及特殊着色子图的存在性这些概念是对图的经典连通性和染色概念的自然而有趣的推广，具有重要的理论研究价值。2001年9月11日美国遭遇恐怖袭击后，由于政府机构之间缺少安全的通信协议，导致相互之间的通信连接出现了重大问题，因此如何加强各机构之间网络通信安全的可靠性立即发展成为了数学科学研究的前沿。而图的彩虹连通性和正常连通性在信息传输和网络安全中有非常重要的作用，因此对这些概念展开研究是非常有意义的。本项目主要研究了非二部图中正常连通数为2的一些充分条件，并探讨了图的正常连通染色的弹性问题，给出了其紧的上界并刻画了相应极图。其次，我们考虑了图的正常k-连通性的算法复杂性问题，得到了k-路连通性的算法复杂性结果。此外，我们还研究了边着色平面图中彩虹子图（匹配、路等）的存在性问题，给出了其相关精确值和上下界。本项目的研究成果主要围绕边着色图的相关理论进行展开，在极值和极图刻画、连通性的算法复杂性方面做了许多工作，进一步丰富了图的连通性和染色方面的理论知识，为后续相关理论的研究提供了新思路和方法。