k-連通圖中最長(zhǎng)圈及余直徑研究.pdf

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

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

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

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

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