图的彩虹连通与广义连通度

The rainbow connections and generalized connectivity of graphs are natural generalizations of the concept of classic connectivity of graphs.Studies of these novel concepts are new development for the important branch, connectivity, of graph theory, and therefore, very significant. Not only as such, but also they have important applications in the designs of secure communication networks and very large scale integration networks. This project is a deeppened continuation of our last project. We will comprehensively make use of the methods and techniques from extremal graph theory, probabilistic methods, random graph theory, and (approximation) algorithm designs and complexity analysis, we well as structural graph theory, etc, to develop deep and systematic methods in the new theories of rainbow connections and generalized connectivity of graphs, in order to solve some existing difficult problems and conjectures, to further sharpen their inequality relations with other garph parameters, to create the Erdos-Gallai type, Bollobas type, Nordhaus-Gaddum type, Merger type, and Nash-Williams-Tutte type results about them, and thus to establish deep connections between these two novel concepts and the classic results and theories in graph theory, with a hope to make new contributions to the two classic branches of graph theory, the connectivity and graph colorings.

图的彩虹连通和广义连通度都是图的经典连通性概念的自然推广，对它们的研究是对图论学科中连通性这一重要分支的新发展，具有重要的理论意义。不仅如此，它们在保密通讯网络的设计和大规模集成电路的设计中都有重要的应用背景。本项目是我们上一研究项目的深入继续，我们将综合地运用极值图论、概率方法、随机图论、(近似)算法设计与复杂性分析、以及结构图论等中的方法和技术，在图的彩虹连通和广义连通度这两个新的研究领域中，发展出深入系统的理论研究方法，解决其中的困难问题和猜想,进一步优化它们与其它图参数之间的不等式关系，创建起有关它们的Erdos-Gallai型、Bollobas型、Nordhaus-Gaddum型、Menger型、 Nash-Williams-Tutte型的结果，从而建立起它们与图论经典结果和理论的深刻联系，以期对图的连通性和染色理论这两个图论学科的经典研究分支做出新贡献。

四年来，本项目在国家自然科学基金的资助下，在项目组成员的一致努力下，取得了丰富的研究成果，完成了项目预期的各项主要目标。发表论文73篇，其中65篇为SCI检索期刊，在Springer等出版著作5部、在高教出版译著1部；培养毕业博士17人、博士后出站5人、硕士1人。.我们的研究工作得到了国际同行学者的广泛关注，应反映前沿研究专题的数学系列丛书Springer Briefs in Mathematics编辑的邀请撰写出版2部专著：Generalized Connectivity of Graphs, Springer 2016， 和 Properly Colored Connectivity of Graphs, Springer (审稿通过，2018年出版）。关于图的彩虹连通数和彩虹连通指标，我们给出图的彩虹连通数分别依据于独立数、块数的紧的上界；利用Szemerédi的正则引理、控制集给出图的k-彩虹指标依据于最小度的上界。关于图的正常连通数，给出一类反例否定了Borozand等在Discrete Math杂志上发表文章中的猜想：对于非完全图G，如果κ(G) = 2，δ(G) ≥ 3，则有 pc(G) = 2；利用Thomassen的结果证明了Magnant的一个猜想的正确性：对于2-连通的非完全图，如果diam(G) = 3，δ(G) ≥ 3，则有 pc(G) = 2；同时，对于另一个猜想：如果阶为n的非完全连通图G满足δ(G) ≥ n/4，则有 pc(G) = 2，证明了它对除了两个阶为7、8的小图外的所有图都成立；证明了随机图的正常连通数为2。关于图的广义连通度，我们解决了关计算复杂性的猜想等。这些结果发表在Discrete Appl. Math., Theoretical Computer Science, Discrete Math., Graphs Combin.,J. Comb. Optim.等杂志上。.除在图的彩虹连通数和广义连通度方面的研究外，我们还在图的能量和其他能量、图熵等其他方面做出了重要的研究结果，解决了Cavers等人提出的奇圈图最大斜谱半径问题的猜想，以及研究随机混合图的谱分布问题，这些结果发表在Electron. J. Combin.， Linear Alg. Appl.等杂志上，并且出版3部相关专著和撰写3章相关综述文章。