图的独立圈和独立团理论的若干结果

来源 :山东大学 | 被引量 : 0次 | 上传用户:ziwen74
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图,对于一个图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.   另外,本文的第三章和第四章中还提出了一些问题,以待进一步研究.
其他文献
第一章是引言及准备知识.第二章引入了强FP∞模的定义,研究了强FP∞模类关于函子Ext1R(-,-)和TorR1(-,-)的右(左)正交类,即S-内射模和S-平坦模.特别地,证明了M是S-内射几模当且仅
由于随机因素往往客观的从在于现实生活中,一般采用确定性方法来研究系统的某些动力学行为,所得出的结论将会发生较大的误差。因此,在系统中考虑随机因素的影响是有必要的。本文
本文对几类拟线性椭圆型方程(组)解的性质进行了研究,主要包括存在性,非存在性,集中性,解集的结构等.   第一章研究以下具有临界非线性项的非线性方程解的存在性和多重性.
图论是一门发展迅速而又应用广泛的新兴学科,它最早起源于一些在民间广泛流传的数学游戏的难题研究,如迷宫问题,博弈问题,棋盘上马的行走路线问题等.其中最早的文字记载出现
自Auslander和Bridge提出有限生成模的Gorenstein维数的概念以来,诸多学者开始了对Gorenstein维数为零的模的研究,尤其是Enochs,Holm等人对Goren-stein投射模的研究,使得这一
本文主要研究具有S-L边值条件正齐次的p-Laplacian方程的分类及其非齐次p-Laplacian方程解的存在性.   在第一章中,我们给出本文要用到的一些预备知识和本文的主要结果. 
拓扑空间X称为几乎可数紧的,如果对于X的任意可数开覆盖(U),存在(U)的有限子集ν使得∪{(V):V∈(V)}=X.在这篇文章中,我们讨论了几乎可数紧空间和可数紧空间的关系,进而研究