k-连通图中最长圈及余直径研究

论文摘要

本论文由三个部分组成.第一部分是对本论文所涉及问题的背景,进展以及所得结果的一个综述.第二部分和第三部分,分别研究k-连通图中的最长圈和余直径.定义k（G）：=k,α（G）：=a,n：=|V（G）|.1972年Chvatal和Erdos[15]证明2个著名定理：若α≤k,则G是哈密顿的；若α<k,则G是哈密顿连通的.存在无数的非哈密顿图满足α≥k+1.1978年Fouquet和Jolivet[29]提出猜想：令G是一n阶k-连通图,满足α≥k≥2,则（详见猜想1.2.12）.第二章首先证明该结论说明当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（G1）∪V（C2）和|V（D1）n V（D2）|≥k（详见猜想2.2.2）.再次证明,若上述2个猜想成立,则Fouquet-Jolivet猜想成立（详见定理1.2.18）.第二章上述结论[11]即将在Journal of Graph Theory上发表.第二章最后证明如下Chvatal-Erdos型定理：如果图G是一n阶k-连通图,其中k≥2,其独立数为a,则（详见定理1.2.20,此结论完全解决了Fouquet-Jolivet猜想）.并证明对任意V0（?）V（G）,G中存在圈C满足（详见定理1.2.27）.第三章证明另一个Chvatal -Erdos型定理：如果图G是一n阶k-连通图,其中k≥2,其独立数为α,则,G中任意2个不同点,要么被一条哈密顿路连接要么被一条长至少为max(k-的路连接（详见定理1.3.7）.另外,对任意V0（?）V（G）和x,y∈V（G）,证明G中存在（x,y）-路P满足（详见定理1.3.10）.最后,我们也提出了可以进一步研究的问题.

论文目录

• 摘要
• ABSTRACT
• 第一章 概述
• §1.1 基本概念和符号
• §1.2 k-连通图周长的下界研究
• §1.3 k-连通图余直径的下界研究
• 第二章 k-连通图周长的下界研究
• §2.1 引言
• §2.2 关于Fouquet-Jolivet猜想研究
• §2.2.1 预备引理
• §2.2.2 定理2.2.1的证明和定理2.2.2的证明
• §2.2.3 猜想之间的联系
• §2.3 根据子图的连通度和独立数对周长的下界研究
• §2.3.1 预备引理
• §2.3.2 定理2.1.3的证明和定理2.1.4的证明
• 第三章 k-连通图余直径的下界研究
• §3.1 引言
• §3.2 一些预备知识和引理
• §3.3 定理3.1.1的证明和定理3.1.3的证明
• §3.4 尚待解决的问题
• 参考文献
• 致谢