论文部分内容阅读
随着大型电子计算机的出现和计算机科学的迅猛发展,特别值得一提的是计算机网络的出现和发展,极大的促进了图论的发展和繁荣,无论在数学,物理,化学,生物等基础学科,还是在交通运输,计算机科学,系统工程等应用领域,图论都显示出越来越重要的作用,因而研究图论问题及其解法具有重要的理论和实际意义。
本文主要研究了图的[a,b]-因子及[a,b]-覆盖图与其顶点度数之间的关系。第一章对研究的背景和现状进行了概述;第二章介绍了与研究有关的一些术语及记号;第三章重点研究图有包含一给定2-因子的[a,b]-因子的度条件;第四章重点研究一个图是[a,b]-覆盖图的邻域并条件。
自从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时该猜想成立。
本文首次给出了图有包含一给定2-因子的[a,b]-因子的度条件及一个图是[a,b]-覆盖图的邻域并条件,从而有利于研究图的因子的存在性及因子-覆盖图与其顶点度数之间的联系。