禁用子图与图中特型支撑树存在性问题研究

The existence problem of spanning trees with some special properties is a hot topic in the research of Structure Graph Theory. It is not only of important theoretical significance, but also of great applied value in the practical fields of computer science, information science and so on. Taking some graphs with forbidden subgraphs as study objects, the project is planned to utilize some basic parameters of graphs including connectivity and degree sum to make a deep research on the relationship between parameters and three types of spanning trees. By applying the segment insertion theory, the extended spanning system theory, the latest methods and techniques in the research of spanning trees with special properties, we will combine the global properties with partial properties of graphs to search for the independent vertex set and analyze its neighborhood properties. We will explore the existence problems of spanning trees with bounded leaves, spanning trees whose stems have bounded leaves and dominating trees with bounded leaves. As a result, the project will contribute to enrich the theoretical system of special spanning trees, which will also help to improve the extensive use and interdisciplinary development of spanning trees theory in computer science and other fields.

图中特型支撑树的存在性问题是结构图论中的一个热门课题，该问题的研究不仅有着重要的理论意义，同时在计算机科学和信息科学等实际领域中也有着很强的应用价值。本项目以不含禁用子图的图类为研究对象，拟运用连通度与度和参数条件，对图中特型支撑树的存在性问题进行深入探讨。我们将利用段插理论、推广的支撑系统理论以及特型支撑树研究的最新技巧和方法，结合图的整体和局部特征，探寻图中点独立集，分析点独立集的邻域特征，试图解决图中具悬挂点数限制的支撑树的存在性问题。本项目的研究将进一步丰富特型支撑树的理论体系，同时推动支撑树理论在计算机科学等领域的广泛应用和交叉发展。