图的参数与支撑树的研究

Spanning tree is an important research topic in the structural of graph theory. The problem is closely related to the development of the problem of Hamilton, which is a famous problem in the graph theory. Spanning tree have a wide range of applications in computer science, organic chemistry, electric network analysis, shortest path design. So it is concerned by many experts of graph theory domestic and overseas. This project is to study a graph to have the given properties of spanning tree, including the following three aspects. First, using the relation between the number of leaves and branch vertices of a tree, we will study a graph to have the spanning trees which have bounded degrees and few leaves. We will give various parameter conditions, for example, the sum degree condition, independence number condition. Second, using the path and circle decomposition theory and the reconstruction method of graph, we will study the decision problem of the k- leaf-connected of graph, and the condition of the independence number will be given. While we will be seeking to the special graph which meet the k-leaf-connected. Finally, by adopting the idea about insertable vertex and segment insertion, we will study graphs (especially high connective graphs) to have given characteristic m-dominating trees. Through the above research, we will explore new techniques in structural of graph, and deepen the understanding of the structure of graph, and promote the development of the structure of graph.

图的支撑树特征问题是结构图论中一个重要的研究课题. 该问题的产生与发展和结构图论中著名的哈密尔顿问题密切相关，并且在计算机科学, 有机化学, 电网络分析，最短连接及渠道设计等领域都有广泛的应用,因此受到国内外图论专家的广泛关注. 本项目拟研究一个图具有给定性质的支撑树所满足的条件，包含以下三个方面的内容. 首先，运用树中叶子点的个数和分支点度和的关系来研究图中存在同时满足给定度条件和叶数限制的支撑树的条件, 给出其度和、 独立数等各种参数条件. 其次，利用图的路及圈的分解理论，采用重构的方法研究图的k-叶连通性的判定问题，并给出其独立数条件，进而拟寻求满足k-叶连通性的特殊图类. 最后，采用可嵌入点和可嵌入路的思想，研究图（特别是高连通图）存在给定特征的m-控制树的参数条件. 我们期待通过以上研究，探讨图的新的论证技巧，加深对图的结构的认识，推动图的结构理论的发展.

图的支撑树特征问题是结构图论中一个重要的研究课题。该问题的产生与发展和结构图论中著名的哈密尔顿问题密切相关，并且在计算机科学，有机化学，电网络分析，最短连接及渠道设计等领域都有广泛的应用。本项目主要应用图的参数研究图是否存在具有哈密尔顿性相关特征的支撑树，以及采用图和组合的分析方法研究网络的限制连通性：我们利用图的路及圈的分解理论，获得连通禁止爪图及高连通禁止爪图存在k-端点支撑树的独立数条件；采用重构的方法，获得图中存在包含给定点的k-树的最优条件；应用图中控制路的分解，解决了Kano等人关于高连通图中存在具有k-端点树干的支撑树的4-稳定集条件。利用图论和组合工具分析互联网络离散结构，完全解决了(n, k)-星图网络、层次立方网络及气泡排序网络的h-超连通度及h-超边连通度问题。发表论文8篇，其中SCI收录5篇。还有1篇已接受即将发表。通过以上研究，丰富了图的支撑树的研究方法，完善了图的结构理论，为后续相关研究提供了参考和指导。