圖中有關(guān)X-圈（路）的一些結(jié)果.pdf

1、設(shè)G=(V, E)為n個點的三連通圖，令X?V(G)．C為G中的圈，如果對于G中任意的圈C’都有|X ∩ V(C)|≥|X ∩ V(C')|，則稱圈C為X-最長圈．我們用α(G)表示圖G的獨立數(shù)，α(X)表示G[X]的獨立數(shù)．當(dāng)尼≤α(X)時σ<,k?(X)表示X中能組成獨立集的尼個點的度和(在G中)最小值；當(dāng)尼>α(X)時令σ<,k>(X)=k(n-α(X))．設(shè)X?V(G)，P為圖G中的路，如果X?V(P)，則稱P為X-路．如果n為

2、正整數(shù)且有n=∑<'k><,i=1> n<,i>且n<,i>≥2(1≤i≤k)，其中n<,i>(1≤i≤k)均為整數(shù)，則稱(n<,1>，n<,2>,…，n<,k>)為m的一個k-分解． 在[4]中鄒園提出如下結(jié)論：G為n個點的三連通圖，C為G中的最長圈，R=G\C，如果σ<,4>(G)≥n+6，那么G[R]中任一連通分支H都滿足|V(H)|≤2．我們可以對條件中的σ<,4>(G)進(jìn)行改動，即取V(G)的一個子集X，將σ<,4>(

3、G)改進(jìn)為σ<,4>(X)，同時對結(jié)論作進(jìn)一步的討論得到本文的第一個結(jié)論：G為n個點的三連通圖，C?V(G)，C為一個X-最長圈，如果σ<,4>(X)≥n+6，那么對于G\C的任一連通分支日，有|V(H)∩ X|≤2，而且恰含兩個X中的點的連通分支不會含X外的點．易見此結(jié)論為[4]中鄒園結(jié)論的推廣． 在[8]中Enomoto等人提出：G為n個點的連通圖，如果有σ<,3>(G)≥n或σ(G)<2，則G有哈密爾頓路或G中的最長圈均為

4、強(qiáng)控制圈．我們對此結(jié)論的一部分進(jìn)行改進(jìn)，得到本文第二個結(jié)論：G為n個點的連通圖，X?V(G)，如果α(X)≤2，那么G有X-路．可見本文第二個結(jié)論推廣了Enomoto的定理的部分結(jié)論． 在[6]中陳耀俊等人給出結(jié)論：G為n個點的連通圖，如果σ<,3>(G)≥(3n-5)/2，那么G有哈密爾頓路．對其進(jìn)行改進(jìn)得到本文的第三個結(jié)論：G為n個點的連通圖，X?V(G)，如果σ<,3>(X)≥(3n-5)/2，那么G有X-路．此結(jié)論為陳耀

5、俊等人結(jié)論的推廣． 同樣，在[7]中Robert Jahansson給出：G為n個點的連通圖，給定n的一個k-分解(n<,1>，n<,2>,…，n<,k>)且n<,i>(1≤i≤k)均為奇數(shù)，如果G有路P使得?<,v>∈V(G)\V(P)在P上都沒有相繼的鄰點且dP(v)≥|n<,1>/2]+|n<,2>2/2]+…+[n<,k>/2]，那么G有點數(shù)分別為n<,1>，n<,2>,…，n<,k>的點不交的路．改進(jìn)此結(jié)論可得本文的第

6、四個結(jié)論：G為n個點的連通圖，X?V(G)，|X|=s，(s<,1>，s<,2>,…，s<,k>)為s的一個k-分解且s<,i>(1≤i≤k)均為奇數(shù)．設(shè)G有路P使得對任意x∈X\V(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)．易見Rober