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

项目名称： 连通图的构造、可去边与相关问题研究

项目编号： No.11301217

项目类型： 青年科学基金项目

立项/批准年度： 2014

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

项目作者： 徐丽琼

作者单位： 集美大学

项目金额： 22万元

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

中文关键词： 连通图；可去边；可收缩边；条件连通度；关联能量

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

英文关键词： connected graph；removable edge；contractible edge；conditional connectivity；incidence energy