关于图的独立圈理论的若干结果

来源 :山东大学 | 被引量 : 0次 | 上传用户:cultra
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图,对于图G,用V(G)和E(G)分别表示图G的顶点集合和边集合,则G=G(V(G),E(G)),对于任意v∈V(G),用dG(v)表示顶点v在G中的度数.用δ(G)即min{dG(v)|v∈V(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,用V1和V2来表示G的两个部分的顶点集合,当|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,y∈V2,xy(?)E(G)}.   (当G是完全二部图时,定义σ1,1=∞).   对于图G中的路P和圈C,分别用l(P)=|V(P)|-1,l(C)=|V(C)|表示路和圈的长度。G的包含G中所有顶点的一个圈称为G的一个哈密顿圈,如果存在G'(?)G使得V(G)=V(G'),则称G'为G的支撑子图,而G的一个1-正则支撑子图就是G的一个1-因子,通常也称1-因子为完美匹配或完美对集.显然G的一个1-因子就是覆盖G中所有顶点的一个边集合.而G的一个2-因子就是G的一个2-正则支撑子图,易知2-因子的每一个连通分支分别是一个圈,而图G的k个独立圈是指G中k个顶点不相交的圈,不难看出2-因子问题与图的独立圈问题有着密切的联系,它们不仅是图的因子理论中非常重要的一部分,也是图的哈密顿圈理论的推广和延伸.其理论研究日益成熟和完善,而且在计算机科学、通信网络设计等领域都有重要的应用.   关于图的独立圈、2-因子理论的研究主要集中在以下几个方面:图中含指定个数的独立圈和2-因子的问题;图中含指定长度的独立圈和2-因子的问题;图中含具有指定性质的独立圈和2-因子的问题等等.   本文的创新之处在于证明的给出过程,采用分层讨论的方法.全文共分三章.第一章简单介绍了图论的基本概念,独立圈,2-因子理论的历史和发展状况及一些已有的相关结论,这一章是后面三章的基础.   第二章讨论了图中包含指定长度的独立圈问题,证明了:定理2.2.1.若|G|=4k,k≥5,σ2(G)≥4k-3,则G包含k-1个点不相交的4-圈,   第三章讨论了二部图中含独立圈的问题,证明了:定理3.1.1.G=(V1,V2;E)是二部图,|V1|=|V2|=3k,k是一个正整数,如果σi,i(G)≥4k-1,那么G包含k-2个6-圈和一个12-圈,并且它们互相独立,
其他文献
Banach空间中渐近非扩张映射的不动点迭代过程是泛函分析中的一个重要研究课题。Banach给出了第一个不动点定理,Mann引入了Mann迭代方法研究非扩张映射不动点的逼近问题,而Ishi
学位
设c是图G的一个边着色,称c为它的强边着色,如果对任何两条边e与e,满足下面条件之一时,c(e)≠c(e):(1) e与e有一个公共的端点;(2)存在一条边e〃与e和e都相邻.一个图G的强边着色数就
在二十世纪中期,Hopf代数引起许多数学家的兴趣,并不断被广泛的研究,得到许多重要的研究成果,有力促进了量子群的研究和发展。在2002年,V.G.Turave引进了一类新的代数结构:Hopfπ-
本文研究一类具有未知概率转移率和混合时滞的离散BAM神经网络的稳定性和同步性问题。相对于概率转移率全部已知或全部未知的情形来说,本文所考虑的情形更具一般代表性,且上述
Cayley图的正规性是一个十分重要的概念,它对对称图与半传递图问题的研究至关重要,所以,一个基本的问题是:对于某类指定的有限群,确定何时它们的Cayleyr图是正规的.这样,我们就可以
在一个班级里面总会有一些学生物理成绩差,这些学生属于物理后进生,一个班的后进生也许不多,但是却会影响整个班级的物理课程的进度,给班级的物理教师带来诸多苦恼.如何将班