关于图的[k,k+1]-因子的若干结果

来源 :东北大学 | 被引量 : 0次 | 上传用户:dvcsvf
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着大型计算机的出现和计算机科学的迅速发展,特别值得一提的是计算机网络的出现和发展,大大地促进了图论的发展和繁荣,无论在数学,物理,化学,生物等基础学科,还是在交通运输,计算机科学,系统工程等应用领域,图论都显示出越来越重要的作用,因而研究图论问题及其解法具有重要的理论和实际意义。 本文主要研究了二分图的哈密顿[k,k+1]-因子与其顶点度之间的关系。第一章对研究的背景和现状进行了概述;第二章介绍了与研究有关的一些术语及记号;第三章重点研究二分图中包含任意给定的哈密顿圈的[k,k+1]-因子的度条件。 自从1952年以来,对图的因子理论的研究进展十分迅速,到现在已有很多的研究成果。图的因子理论与很多图论中的其它知识有关,如图的因子与坚韧度之间有联系。1971年,Chvatal提出了下面的猜想:若图G是3/2-坚韧的,则G有2-因子。该猜想至今未得到证实。图的因子与其顶点度数之间也有紧密地联系,1992年,T.Nishimura提出了下面的猜想:设G是一个n阶图,对任意x,y∈V(G),如果x与y之间的距离dG(x,y)=2,且max{dG(x),dG(y)}≥n/2,n≥4k-3,kn为偶数,则图G有k-因子。该猜想也没有完全解决,1997年钱建波证明了该猜想对二分图成立,同年T.Niniessen证明了当n≥8k2+12k+6时该猜想成立。1998年蔡茂诚给出了:设G是一个n阶图,对不相邻的两个顶点x,y∈V(G),如果dG(x)+dG(y)≥n,则图G中包含任意给定的哈密顿圈C的[k,k+1]-因子。2002年,H.Matsuda[14]改进为:设k为正整数,且k≥2,G是阶|G|≥3的2-连通图,δ(G)≥k,对偶数|G|有|G|≥8k-16且对奇数|G|有|G|≥6k-13,如果G中每一对不相邻的顶点x和y有max{dG(x),dG(y)}≥|G|/2则对G的任意哈密顿圈C,G有[k,k+1]-因子包含圈C。 本文给出了二分图中包含任意给定的哈密顿圈C的[k,k+1]-因子的度条件,即:1.设G是顶点数为n的均衡二分图,且是n/4+1临界图,n≥8k-12,n≥12,k≥2,则对G的任意哈密顿圈C,G有[k,k+1]-因子包含圈C。 2.设k≥2,G=(X,Y,E)中,|X|=|Y|=n/2≥4(k-2)-1,n≥6,δ(G)≥k,k为正整数。如果G的每一对距离为2的顶点u,v有max{dG(u),dG(v)}≥n/4+2,则对G的任意哈密顿圈C,G有[k,k+1]-因子包含圈C。 3.设G=(X,Y,E),|X|=|Y|=n/2≥4(k-2)-3,k≥2且n≥6,δ(G)≥k,若G中每一对不相邻的顶点u,v有max{dG(x),dG(x)}≥n/4+2,则G有包含哈密顿圈C的[k,k+1]-因子。 4.设二分图G=(X,Y,E),|X|=|Y|=n/2≥4(k-2)-3,k≥2且n≥6,δ(G)≥k,若G中每一对不相邻的顶点u,v有dG(u)+dG(v)≥n/2+4,则G有包含哈密顿圈C的[k,k+1]-因子。 此度条件改进了阶为n的图G包含任意给定的哈密顿圈C的[k,k+1]-因子的度条件,从而大大地促进了哈密顿[k,k+1]-因子的研究与发展。
其他文献
该文在时间序列坐标延迟后重构的相间中,作出重构函数的等价定义,提高了预测的可操作性;并在此基础上,引入了加权距离来刻画预测向量的邻近点,保证了邻近点的相似性.用多邻近
学位
  本文建立了互连网络拓扑结构的超连通度(超边连通度)和限制可诊断数研究的基本理论和方法,并且得到了几个著名的网络拓扑结构的超连通度(超边连通度)和限制可诊断数以及折
本文利用文[3]给出的单参数李群理论,研究了一些自治系统在接受多个相互独立的单参数李群时,如何求出系统的首次积分的问题.研究的主要内容和结果包括以下几个方面: (1)当3阶
本文以凸多胞形的几何不等式为主要研究内容,此外对凸函数以及i弦对称体也做了一定的研究.首先在第一章第一节介绍了凸体几何的发展历史以及国内外数学工作者在凸多胞形的几何
利用小波变换像空间与再生核空间的联系,本文给出了一种在再生核空间中重建小波变换的方法。首先,针对Mallat极大模重建小波变换算法没有充分利用信号突变点的不足,建立了一个更
  本文给出加法交换半环上的平移壳,并且给出半环的坚强分配格的结构,最后给出了逆半环的核正规系。具体内容如下:  第一章,给出引言和预备知识。  第二章,首次给出加法交换