图的子图存在性问题是图论的一个重要的研究领域,它和图的染色问题及极值图论等有着非常密切的关系。本项目主要研究图的点不相交子图的存在性,关于这个课题还有很多问题没有解决。首先,本项目研究最小度、最小度和、领域并等不同度条件下点不相交圈的存在性,继续深入讨论图的具有指定长度的圈的存在性,同时力求每个圈包含尽可能多的弦。此外,我们还从另外一个角度来研究图的点不相交子图的存在性,即在图的度条件很弱的情况下,通过增加顶点数等条件,使得图包含一些点不相交的子图,并力求寻找顶点数的最好下界。本项目的研究涉及到组合数学,极值图论,计算机网络及生物信息学,问题的解决对图论,计算机科学及生物信息学等学科的发展都有重要的意义。
围绕图中点不相交子图的存在性这个问题,本项目研究了最小度、最小度和、领域并等不同度条件下点不相交圈的存在性,深入讨论了图中圈的长度和弦的数量,同时研究了度条件很弱的情况下,图中点不相交子图的存在性,力求寻找顶点数的最好下界。通过这些内容的研究,得到了最小度条件下图包含点不相交的带弦8圈、最小度和条件下无爪图包含点不相交的4圈、最小度为4的图包含k个点不相交的子图K1+(K1∪K2)所需要的最小顶点数、图中具有相同长度的圈等结果。我们圆满完成了研究计划,取得了一系列的具有独创性的结果。本项目的研究涉及到组合数学,极值图论,计算机网络及生物信息学等学科,问题的解决对组合数学,图论,计算机网络及生物信息学等的发展都有重要的意义。