论文部分内容阅读
本文主要介绍图中的圈及其相关问题。
本文首先对2-因子问题做了研究,哈密尔顿问题作为图论中的一个重要分支,在图论的发展中有着举足轻重的地位,由此延伸出的因子理论更是近年来研究的热点之一。本文对2-连通的无爪图进行研究,证明了如下结果:
结果:1
图G为2-连通的无爪图,n≥51,如果对G中任意不相邻的两顶点x,y,满足度条件:d(x)+d(y)≥2n-4/3,那么对任意的正整数k,若2≤k≤n-24/3,下列情况之一成立:
(1)图G含有一个2-因子恰包含k个分支;
(2)图G恰包含k个顶点不交的圈G1,C2,…,Ck和一个导出子图为完全图的子图H,使得,V(G)=V(C1)U V(C2)U…U V(Ck)U V(H)。
接下来本文对彩色问题做了研究,染色问题也是图论中的一大重要分支,正常染色圈问题作为染色问题和因子理论的结合,在图论中有着重要地位,本文对不含三角形的边染色图进行研究,主要证明了如下结果:
结果:2
图G为最小色度d≥2的边染色图,若G中不含三角形,则G含有长度至少为4d-2的正常染色路或含有长度为2d-2的正常染色圈。
最后本文对群连通理论作了研究,群连通理论作为证明染色问题的一个重要工具,与圈覆盖有着密切的联系,本文对3-正则图进行研究,主要证明了下列结果:
结果:3
一个连通的3-正则图是Z3-连通当且仅当G不同构于本文中的2个图(图1和图2)。