论文部分内容阅读
随着大型计算机的出现和计算机科学的迅速发展,特别值得一提的是计算机网络的出现和发展,大大地促进了图论的发展和繁荣,无论在数学,物理,化学,生物等基础学科,还是在交通运输,计算机科学,系统工程等应用领域,图论都显示出越来越重要的作用,因而研究图论问题及其解法具有重要的理论和实际意义。
本文主要研究了二分图的哈密顿[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]-因子的研究与发展。