论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图,对于一个图G=G(V(G),E(G)),我们用V(G)和E(G)分别表示图的顶点集合和边集合.对任意的u∈V(G),我们用dG(v)表示顶点v在G中的度数.△(G)和δ(G)分别表示图G的最大度和最小度,在不引起混淆的情况下简记为△和δ.对于图G,我们用|G|=|V(G)|表示G的阶数,即G的顶点数,并定义图G中两个不相邻的顶点的最小度和为:σ2(G)=min(dG(x)+dG(y)|x,y∈V(G),x≠y,xy(∈)E(G)).(若G是一个完全图,则令σ2(G)=∞).
对于二部图G,令G的两个部分的顶点集合分别为V1和V2.若|V1|=|V2|,则称G为均衡二部图.定义δ1,1(G)=min(dG(x)+dG(y)|x∈V1,y∈V2),σ1,1(G)=min(dG(x)+dG(y)|x∈V1,u∈V2,xy(∈)E(G)).(若G是一个完全二部图,则令σ1,1=∞).
完全二部图K1,3称为一个爪,如果G不含同构于K1,3的生成子图,则称G是无爪图.对于图G中的一条路P和一个圈C,定义路和圈的长度分别为:l(P)=|V(P)|-1,l(C)=|V(C)|.
G的一个哈密顿圈是G的包含G中所有顶点的一个圈.G的一个1-因子是G的一个1-正则支撑子图,通常我们称1-因子为完美对集或完美匹配.显然G的一个1-因子是覆盖G的所有顶点的一个边集合.G的一个2-因子是G的一个2-正则支撑子图,易见2-因子的每一个连通分支为一个圈.图的k个独立圈是指G中k个顶点不相交的圈.
图的独立圈、2-因子和路因子问题是图的因子理论中非常重要的一部分,也是图的哈密顿圈理论的推广和延伸.其理论研究日益成熟和完善,而且它在计算机科学、通信网络设计等中都有重要应用.关于图的独立圈、2-因子和路因子理论的研究主要集中在以下几个方面:图中含指定个数的独立圈和2-因子;含指定长度的独立圈和2-因子;图中具有指定性质的独立圈和2-因子;具有指定性质的路因子等等.
本文的创新之处在于讨论了图中包含指定个数的阶为3和4的独立团问题.全文共分四章.第一章简单介绍了图论的基本概念,圈因子理论的历史和发展状况及一些已有的相关结论,这一章是其余三章的基础.
第二章讨论了图中包含指定长度的独立圈问题,证明了如下结论:定理2.1.1设k和s是两个非负整数,且k≥s.简单图G满足n=|G|≥3s+4(k-s)+7.如果σ2(G)≥n+s,那么G中包含一个由k+1个圈C1,,Ck+1所组成的2-因子,满足l(Ci)=3其中1≤I≤s-1,l(Ci)=4其中s≤I≤k-3,l(Ci)≤4其中k-2≤I≤k-1,且有l(Ck)∈(3,4,7,8).
第三章讨论了图中包含指定长度的独立团的问题.其主要结果如下:定理3.1.1设k和s是两个非负整数,且k≥s,简单图G满足n=|G|≥3s+4(k-s).如果σ2(G)≥3(n-s)/2+k-1,那么G包含互不相交的s个3-团和k-s个4-团的并,即G(つ-)sK3+(k-s)K4.
在第四章中我们考虑了非空无爪图中含指定长度的独立团的问题,并证明了如下定理:定理4.1.1设k和s是两个非负整数,且k≥s,设简单图G是一个非空的无爪图,且满足n=|G|≥3s+4(k-s).如果图中任意相邻两点的度数和β(G)≥3n-s-1/2,那么G包含互不相交的s个3-团和k-s个4-团的并,即G(つ-)sK3+(k-s)K4.
另外,本文的第三章和第四章中还提出了一些问题,以待进一步研究.