连通图的构造、可去边与相关问题研究

The theory of connectivity of graph is an important part of graph theory, which has a close relation with network optimization problems，such as network reliability(fault tolerance), etc. The construction of connected graphs is one of core problem in the theory of connectivity of graph,it is a forefront reserch topic which has been very concerned by many experts at home and abroad. Including one of the modern graph theory founders, Royal Canadian Academy of Sciences- - - Professor Tutte, and a famous German scholar- - -Professor Mader,etc.all have important research results on this problems. Up to now, the construction of minimally k-connected graphs for k≥4 is still an open problem. The aim of this project is to investigate the construction of minimally k-connected graphs by combining the properties of removable edges and contractible edges in minimally k-connected graphs.The content of this projecct also contains removable edge which is related to the construction of connected graph closely. We will sdudy the distributions of removable edges in certain substructures of k-connected graphs and minimally k-connected graphs,such as outside the spanning tree,maximal matching,etc. We will also investigate the relationship between restricted edge-connectivity、(edge) neighbor connectivity of product graphs and indexes of factor graphs. The expected results of the project will provide the theoretical basis for the study on the fields of network optimization and combinatorial optimization, which have important theoretical significances and practical meanings.

图的连通性理论是图论的重要组成部分，与网络的可靠性(容错性)等网络优化问题密切相关。连通图的构造是连通性理论的核心问题之一，它一直是国内外学者非常关注的前沿研究课题。现代图论的奠基人之一加拿大科学院院士Tutte教授、德国著名学者Mader教授等对这个问题都有重要研究。对于k≥4,极小k连通图的构造问题至今仍是一个困难的未解决问题。本项目将结合极小k连通图中的可去边和可收缩边的性质来研究极小k连通图的构造。与连通图构造密切相关的可去边也是本项目的研究内容。我们将研究k连通图和极小k连通图中可去边在生成树外、最大匹配等特殊子图上的分布问题。我们也将研究各种乘积图的限制边连通性、（边）邻域连通性与因子图的各指标之间的关系。本项目预期成果将为网络优化和组合优化等领域的研究提供理论依据，具有重要理论意义和实际应用价值。

图的连通性理论是图论的重要组成部分，与网络的可靠性(容错性)等网络优化问题密切相关。连通图的构造是连通性理论的核心问题之一，它一直是国内外学者非常关注的前沿研究课题。现代图论的奠基人之一加拿大科学院院士Tutte教授、德国著名学者Mader教授等对这个问题都有重要研究。对于k≥4,极小k连通图的构造问题至今仍是一个困难的未解决问题。本项目结合极小4连通图中的可去边性质得到极小4连通图的构造；同时我们得到3连通图和极小3连通图中可去边在生成树、最大匹配等特殊子图上的分布问题。我们也得到某些网络模型的条件连通度和条件诊断度等以及某些图的关联能量的性质等结果。本项目成果将为网络优化和组合优化等领域的研究提供理论依据，具有重要理论意义和实际应用价值，已发表或录用文章10篇，已投稿文章5篇。