论文部分内容阅读
本文主要研究图中点不交的圈的个数问题。如果两个圈没有共同的顶点，则称这两个圈是点不交的或是独立的。我们定义这样一类图Fl，k，n，l，k，n是三个整数，l是奇数，n-sk+1是偶数，并且s=l+1/2,当且仅当V(G)有一个划分(X，Y,Z)使得|X|=sk-1,|Y|=|Z|=n-2k+1/2,这个划分满足如下条件:Y和Z之间有n-sk+1/2条边，X和Z之间没有边，X中的每一个点与Y中的每一个点相连，且对于X中的边没有限制。 本文对图中独立圈的个数问题进行了研究，独立圈的个数问题是图论中一个重要的问题，在图论的发展中有着很重要的地位，许多学者对图中的独立圈个数进行了研究， Hong Wang在[22]中证明了下面的结果: (1)设k是一个正整数，图G是一个点数为n≥3k的连通图，设G中任意距离为2的两个顶点x，y，满足度条件:d(x）+d(y)≥4k。若G中含t个点不交的圈C1,C2,…Ct，G-∪ti=1Ci中不含圈含一条点数为s＞4的路，则G包含k个独立圈或者n是奇数G属于F3,k，n。 本文证明了下面的结果: (2)设k是一个正整数，图G是一个点数为n≥3k的连通图，设G中任意距离为2的两个顶点x，y，满足度条件:d(x）+d(y)≥4k。若G中含t个点不交的圈C1,C2,…Ct，G-∪ti=1 Ci中不含圈含一条点数为s≤4的路，则G包含k个独立圈。 综合两个结果得到下面的结论: 设k是一个正整数，图G是一个点数为n≥3k的连通图，如果G中任意距离为2的两个顶点x，y，满足度条件:d(x）+d（y）≥4k，则G包含k个独立圈或者n是奇数G属于F3,k，n。 丁录顺在[11]中证明了下面的结论: (1)设图G为2-连通的无爪图，n≥51,如果对G中任意不相邻的两顶点x，y，满足度条件:d(x)+d（y）≥2n-4/3,那么对任意的正整数k，若2≤k≤n-24/3,下列情况之一成立: (1)图G含有一个2-因子恰包含k个分支; (2)图G恰包含k个顶点不交的圈C1,C2,…，Ck和一个导出子图为完全图的子图H，使得V(G)=V(C1)∪ V(C2)∪…∪ V(Ck)∪ V(H)。 在上述结论的证明过程中可以得到，若G-∪ki=1 Ci中存在一个点v使得d(v)＞n-2/3,则(1)成立，若对于任意的点v∈G-∪ki=1 Ci有d(v)＜n-2/3,则(2)成立。 本文证明了下面的结果: (2)设图G是一个顶点数为n≥68的2-连通的无爪图，如果G中任意不相邻的两顶点x，y，满足度条件:d(x)+d(y)≥2n-4/3,那么对任意的正整数k，若1≤k≤n-24/3,若G中包含k个点不交的圈C1,C2…，Ck，且对于G-∪ki=1Ci中任意一个点v，有d(v)＜n-2/3,则G恰好含有k个圈C1,C2…，Ck使得G-∪ki=1Ci中至多有一个点v满足d(v)＜n-2/3。 综合上面两个结果得到下面的结论: 设图G是一个顶点数为n≥68的2-连通的无爪图，如果G中任意不相邻的两顶点x，y，满足度条件:d(x)+d(y)≥2n-4/3,那么对任意的正整数k，若1≤k≤ n-24/3,则G恰好含有k个圈C1,C2…，Ck使得G-∪ki=1Ci中至多有一个点v满足d(v)＜n-2/3。 对于图中不交的三圈，我们得到了下面的结果: 设k≥1是一个整数，图G是一个顶点数为n的2-连通的无爪图，如果n＞3k+3并且对G中任意不相邻的两顶点x，y，满足度条件:d(x)+d（y）≥2k+2,△(G)≥3,则G包含k个独立的三圈。