k-連通圖中最長圈及余直徑研究.pdf

1、本論文由三個部分組成.第一部分是對本論文所涉及問題的背景,進展以及所得結(jié)果的一個綜述.第二部分和第三部分,分別研究k-連通圖中的最長圈和余直徑.
　　 定義k(G):=k,α(G):=α,n:=|v(G)|.1972年Chvátal和Erd(o)s[15]證明2個著名定理:若α≤k,則G是哈密頓的;若α＜k,則G是哈密頓連通的.存在無數(shù)的非哈密頓圖滿足α≥k+1.1978年Fouquet和Jolivet[29]提出猜想:令G是-

2、n階肛連通圖,滿足α≥k≥2,則c(G)≥k(n+α-k)/α(詳見猜想1.2.12).第二章首先證明c(G)≥k(n+α-k)/α-(k-3)(k-4)/2,該結(jié)論說明當k=4時Fouquet-Jolivet猜想成立(詳見定理1.2.16).其次證明當K≥α-3時Fouquet-Jolivet猜想成立(詳見定理1.2.17).類似于Kouider[40]中的結(jié)論,進一步提出猜想:對每個圖G,令u,v是G中任意兩個不同點.則,要么V(G

3、)存在一個非平凡的劃分V1∪V2滿足α(G)=α(G[V1])+α(G[V2]),要么G中存在一條(u,v)一路P滿足α(G-V(P))≤α(G)-1.(詳見猜想2.2.6).J.Chen等[14]研究最長圈之間的交集并提出猜想:令G是k-連通圖,令C1和C2是G中任意2個不同圈,則G中存在2個不同圈D1和D2,滿足V(D1)∪V(D2)(∪)V(C1)∪V(G)和|V(D1)∩V(D2)|≥k(詳見猜想2.2.2).再次證明,若上述2

4、個猜想成立,則Fouquet-Jolivet猜想成立(詳見定理1.2.18).第二章上述結(jié)論[11]即將在Journal ofGraph Theory上發(fā)表.第二章最后證明如下Chvátal-Erd(o)s型定理:如果圖G是-n階k-連通圖,其中k≥2,其獨立數(shù)為α,則c(G)≥min{n,max{k(n+α-k)/α,k「n=2α-2k/α」}}(詳見定理1.2.20,此結(jié)論完全解決了Fouquet-Jolivet猜想).并證明對任意

5、V0(∈)V(G),G中存在圈c滿足|V(C)∩ V0}≥min{|V0|,k「|V0|+α(V0)-k/α(V0)」}(詳見定理1.2.27).
　　 第三章證明另一個Chvhátal-Erd(o)s型定理:如果圖G是-n階k-連通圖,其中k≥2,其獨立數(shù)為α,則,G中任意2個不同點,要么被一條哈密頓路連接要么被一條長至少為max(k-1){n+α-k/α,「n+2α-2k+1/α」}的路連接(詳見定理1.3.7).另外,對任