论文部分内容阅读
本论文由三个部分组成.第一部分是对本论文所涉及问题的背景,进展以及所得结果的一个综述.第二部分和第三部分,分别研究k-连通图中的最长圈和余直径.
定义k(G):=k,α(G):=α,n:=|v(G)|.1972年Chvátal和Erd(o)s[15]证明2个著名定理:若α≤k,则G是哈密顿的;若α<k,则G是哈密顿连通的.存在无数的非哈密顿图满足α≥k+1.1978年Fouquet和Jolivet[29]提出猜想:令G是-n阶肛连通图,满足α≥k≥2,则c(G)≥k(n+α-k)/α(详见猜想1.2.12).第二章首先证明c(G)≥k(n+α-k)/α-(k-3)(k-4)/2,该结论说明当k=4时Fouquet-Jolivet猜想成立(详见定理1.2.16).其次证明当K≥α-3时Fouquet-Jolivet猜想成立(详见定理1.2.17).类似于Kouider[40]中的结论,进一步提出猜想:对每个图G,令u,v是G中任意两个不同点.则,要么V(G)存在一个非平凡的划分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个猜想成立,则Fouquet-Jolivet猜想成立(详见定理1.2.18).第二章上述结论[11]即将在Journal ofGraph Theory上发表.第二章最后证明如下Chvátal-Erd(o)s型定理:如果图G是-n阶k-连通图,其中k≥2,其独立数为α,则c(G)≥min{n,max{k(n+α-k)/α,k「n=2α-2k/α」}}(详见定理1.2.20,此结论完全解决了Fouquet-Jolivet猜想).并证明对任意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,其独立数为α,则,G中任意2个不同点,要么被一条哈密顿路连接要么被一条长至少为max(k-1){n+α-k/α,「n+2α-2k+1/α」}的路连接(详见定理1.3.7).另外,对任意V0(∈)V(G)和x,y∈V(G),证明G中存在(x,y)-路P满足|V(P)∩V0|≥min{|V0|,(k-1)「|V0|+α(V0)-(k-1)/α(V)0」}(详见定理1.3.10).
最后,我们也提出了可以进一步研究的问题.