图中独立4-圈与独立6-圈的相关结论

来源 :山东大学 | 被引量 : 0次 | 上传用户:zhuanzhiboke
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图若无特殊声明均为简单、无向有限图,对于一个图G=G(V(G),E(G)),我们用V(G)和E(G)分别表示图的顶点集合和边集合.对任意的v∈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,y∈V2,xy (∈)E(G)). (若G是—个完全二部图,则令σ1,1=∞). 图的—个路因子就是指每一个分支都是一条路的一个生成子图.给定—个正整数k,P≥k-因子就是指每个分支都至少含k个顶点的一个路因子. 对于图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-因子;具有指定性质的路因子等等. 全文共分四章.第一章简单介绍了图论的基本概念,圈和路因子理论的历史和发展状况及一些已有的相关结论.这一章是第二章和第三章的基础. 第二章讨论了含4k个顶点的简单图的结构和度条件的部分结果.其主要结果如下: 定理2.1.1.设G是一个有4k个顶点的简单图,其中k是一个正整数,如果σ2(G)≥4k-2,则G包含k-1个点不相交的4-圈Ci,i=1,2,…,k-1,并且e((G-V(Uk-1 i=1 Ci)))≥2. 本文第三章中我们考虑了含6七个顶点的二部图的结构和度条件,提出了用6-圈与12-圈去划分二部图,还有用6-圈去划分二部图.主要证明了如下几个结论. 定理3.1.1.设k≥2是一个正整数,G是有6k个顶点的均衡二部图,︱V1 ︱=︱V2︱=3k,δ1,1(G)≥4k-1,则G包含k-1个点不相交的6-圈. 定理3.1.2.设G是有6k(k≥5)个顶点的均衡二部图,︱V1︱=︱V2︱=3k,δ1,1(G)≥4k-1,则G可以划分为k-2个6-圈和一个12-圈,并且这k-1圈点不相交. 定理3.2.1.设G为二部图,︱V1︱=︱V2︱=3k,δ1,1(G)≥4k+1,则G包含k个6-圈。 本文第四章主要给出了关于满足一定度条件的图不含指定点的独立圈问题的注释. 另外,本文的第二章和第三章最后还提出了一些问题,以待进一步研究.
其他文献
近几年来,功能梯度材料的概念被引入到工程结构中来.由于这种材料有很大的优越性,因此,人们对功能梯度材料的研究越来越重视了.其应用领域涉及航天、航空、核能源、电子学、
混沌就是指在确定性系统中出现的貌似无规则的类似随机的现象。近来人们发现人脑中存在着混沌现象,混沌理论可解释人脑中某些不规则的活动,因此,混沌动力学为人们研究神经网络提
本文主要研究非单调技术和过滤集技术在最优化和非光滑方程组中的应用.在光滑非线性优化和非线性方程组问题中,过滤集技术已获得了成功的应用.现在,我们把过滤集技术引入到非光
电磁轴承系统是一个非线性控制系统,电磁控制力是被控对象的位移和控制电流的非线性函数。当系统参数位于某些区域时,非线性力的作用会使转子产生相当大的振动,所以分析系统的非线性振动特性、稳定性等动力学性质是电磁轴承系统研究的重要课题。另外,在电磁轴承控制系统中不可避免地带有时滞。时滞的存在使动力系统的相空间由有限维变成了无穷维,并可能带来系统稳定性、周期解的存在性等动力学性质的变化。考虑时滞的影响,可以
由不同材料性质的介质沿界面组成一体的材料称为“双材料”。由于这种双材料具有单一材料所不具有的综合性能,因而在工程上的应用范围不断扩大,尤其是被广泛地应用于航空、航
图谱理论是图论研究的一个非常活跃的重要领域,它在量子化学、统计力学、通信网络及信息科学中均有一系列重要应用。图谱理论的研究主要是利用线性代数、矩阵理论等成熟的代数
远景交通量预测分析是路网规划的重要内容,是交通基础设施建设项目可行性研究的基础和前提,是投资规模以及经济评价的主要依据。传统的城市交通“四阶段”法关键在于交通出行生