连通图的可去边、可收缩边与条件连通性理论

项目名称： 连通图的可去边、可收缩边与条件连通性理论

项目编号： No.10801091

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

立项/批准年度： 2009

项目学科： 轻工业、手工业

项目作者： 吴吉昌

作者单位： 山东大学

项目金额： 17万元

中文摘要： 本项目的研究内容主要有两部分：一部分是关于连通图的可去边和可收缩边，另外一部分内容是条件连通性理论。我们得出结果如下：（1）4连通图的Hamilton圈上以及任意圈外的可去边的分布情况，得出了4连通图哈密顿圈上在不同的条件下包含可去边的数目.并实例说明这些结果是不可改进的。（2）运用可去边的性质，部分证明Tomassen关于3连通图的最长圈与弦的理论猜想。以上结果均投出。（3）研究了正则图的3限制边连通性的优化理论，得到了相应的优化方法。（4）还研究了5类乘积网络拓扑结构的限制连通度优化方法。研究了无环分子的电子能量的极值问题，给出了树形分子图的能量极值化的图形转化方法，并给出了这些分子图依能量的排序，研究结果得到国际量子化学界资深学者I.Gutman的高度评价，将发表在量子化学顶级期刊上。（5）研究了图的条件连通性优化理论及其在网络优化理论中的应用，给出了正则网络拓扑与常见乘积图的限制连通性优化方法，并将其应用于超立方体网络的可靠性估计之中。（6）探讨了某些重要化学指标取得极值时的化学分子拓扑结构，刻画了具有极大能量的单圈分子图，给出了无圈分子图依能量的排序。

中文关键词： 可去边；限制边连通性；网络可靠性；能量

英文摘要： This work studies both removable edges and contractible edges in connected graphs and the optimization of conditional connectivity of graphs and its application in optimization of networks. For removable edges and contractible edges we get the following conclusions: (1) We study the distribution of removable edges outside a cycle or on the Hamilton cycle in a 4-connected graph. We give Examples to show that our some results are best possible in some sense. (2) We prove that Thomassen's conjecture is true for two classes of 3-connected graphs. (3) For the optimization of conditional connectivity of graphs and its application in optimization of networks, we study the schemes on optimizing restricted edge connectivity of regular networks and usual product graphs are presented, the application of these schemes in the estimation of reliability of networks results in desired observations. Extremal molecular topologies according to some important chemical indices are considered, as a result, unicyclic molecular graphs with maximal energy is characterized, as well as the ordering of acyclic molecular graphs on their energy.

英文关键词： removable edges; restricted edge connectivity; network reliability; energy