图的点不相交子图

The existence of subgraphs in a graph is an important area of research in graph theory, which is closely related to graph coloring problem, extremal graph theory and so on. The project is mainly focus on the existence of vertex-disjont subgraphs, and there are so many problems unsolved in this area. Firstly, this project will discuss the existence of vertex-disjoint circle with minimum degree, minimum degree sum, neighborhood union and other different degree conditions, study the existence of cycles with given length and ensure each cycle have as many chords as possible. What’s more, this project will focus on the existence of vertex-disjoint subgraphs from another point. That is, making the graphs with weak degree contain some vertex-disjoint subgraphs by adding the number of vertices, and furthermore searching the best lower bound of the number of vertices. The study of this project involves combinatorial mathematics, extremal graph theory, computer networks, and bio-information science. The solution to this project is of great significance to the development of graph theory, computer science, bio-information science and other disciplines.

图的子图存在性问题是图论的一个重要的研究领域，它和图的染色问题及极值图论等有着非常密切的关系。本项目主要研究图的点不相交子图的存在性，关于这个课题还有很多问题没有解决。首先，本项目研究最小度、最小度和、领域并等不同度条件下点不相交圈的存在性，继续深入讨论图的具有指定长度的圈的存在性，同时力求每个圈包含尽可能多的弦。此外，我们还从另外一个角度来研究图的点不相交子图的存在性，即在图的度条件很弱的情况下，通过增加顶点数等条件，使得图包含一些点不相交的子图，并力求寻找顶点数的最好下界。本项目的研究涉及到组合数学，极值图论，计算机网络及生物信息学，问题的解决对图论，计算机科学及生物信息学等学科的发展都有重要的意义。

围绕图中点不相交子图的存在性这个问题，本项目研究了最小度、最小度和、领域并等不同度条件下点不相交圈的存在性，深入讨论了图中圈的长度和弦的数量，同时研究了度条件很弱的情况下，图中点不相交子图的存在性，力求寻找顶点数的最好下界。通过这些内容的研究，得到了最小度条件下图包含点不相交的带弦8圈、最小度和条件下无爪图包含点不相交的4圈、最小度为4的图包含k个点不相交的子图K1+(K1∪K2)所需要的最小顶点数、图中具有相同长度的圈等结果。我们圆满完成了研究计划，取得了一系列的具有独创性的结果。本项目的研究涉及到组合数学，极值图论，计算机网络及生物信息学等学科，问题的解决对组合数学，图论，计算机网络及生物信息学等的发展都有重要的意义。