论文部分内容阅读
设G=(V, E)为n个点的三连通图，令X?V(G)．C为G中的圈，如果对于G中任意的圈C’都有|X ∩ V(C)|≥|X ∩ V(C)|，则称圈C为X-最长圈．我们用α(G)表示图G的独立数，α(X)表示G[X]的独立数．当尼≤α(X)时σ<,k?(X)表示X中能组成独立集的尼个点的度和(在G中)最小值；当尼>α(X)时令σ<,k>(X)=k(n-α(X))．设X?V(G)，P为图G中的路，如果X?V(P)，则称P为X-路．如果n为正整数且有n=∑<,i=1> n<,i>且n<,i>≥2(1≤i≤k)，其中n<,i>(1≤i≤k)均为整数，则称(n<,1>，n<,2>,…，n<,k>)为m的一个k-分解．
在[4]中邹园提出如下结论：G为n个点的三连通图，C为G中的最长圈，R=GC，如果σ<,4>(G)≥n+6，那么G[R]中任一连通分支H都满足|V(H)|≤2．我们可以对条件中的σ<,4>(G)进行改动，即取V(G)的一个子集X，将σ<,4>(G)改进为σ<,4>(X)，同时对结论作进一步的讨论得到本文的第一个结论：G为n个点的三连通图，C?V(G)，C为一个X-最长圈，如果σ<,4>(X)≥n+6，那么对于GC的任一连通分支日，有|V(H)∩ X|≤2，而且恰含两个X中的点的连通分支不会含X外的点．易见此结论为[4]中邹园结论的推广．
在[8]中Enomoto等人提出：G为n个点的连通图，如果有σ<,3>(G)≥n或σ(G)<2，则G有哈密尔顿路或G中的最长圈均为强控制圈．我们对此结论的一部分进行改进，得到本文第二个结论：G为n个点的连通图，X?V(G)，如果α(X)≤2，那么G有X-路．可见本文第二个结论推广了Enomoto的定理的部分结论．
在[6]中陈耀俊等人给出结论：G为n个点的连通图，如果σ<,3>(G)≥(3n-5)/2，那么G有哈密尔顿路．对其进行改进得到本文的第三个结论：G为n个点的连通图，X?V(G)，如果σ<,3>(X)≥(3n-5)/2，那么G有X-路．此结论为陈耀俊等人结论的推广．
同样，在[7]中Robert Jahansson给出：G为n个点的连通图，给定n的一个k-分解(n<,1>，n<,2>,…，n<,k>)且n<,i>(1≤i≤k)均为奇数，如果G有路P使得?<,v>∈V(G)V(P)在P上都没有相继的邻点且dP(v)≥|n<,1>/2]+|n<,2>2/2]+…+[n<,k>/2]，那么G有点数分别为n<,1>，n<,2>,…，n<,k>的点不交的路．改进此结论可得本文的第四个结论：G为n个点的连通图，X?V(G)，|X|=s，(s<,1>，s<,2>,…，s<,k>)为s的一个k-分解且s<,i>(1≤i≤k)均为奇数．设G有路P使得对任意x∈XV(P)都有|N<,P>(x)∩X|≥「s<,1>/2」+「s<,2>/2」+…+「s<,k>/2」且x在P上不会有相继邻点都在X中，那么G有点不交的路P<,1>，P<,2>,…，P<,k>使|P<,i>∩X|=s<,i>(i=1，2,…，k)．易见Robert Jahansson的结论为本文的第四个结论的推论．在最后一章，我们提出了一些在今后研究中可以思考的问题．