论文部分内容阅读
图的哈密尔顿性是结构图论的重要研究课题.该问题与著名的四色猜想密切相关,因而受到众多图论专家的关注.从计算复杂性角度看,判定一个图是否为哈密尔顿图是NP-困难的,所以对哈密尔顿问题的研究主要集中在给出判定一个图为哈密尔顿图的充分条件。
目前已有的关于哈密尔顿图的充分条件主要包含两类:一类是从参数的角度刻画,常用的有最小度、度和、独立数、邻域并等;另一类是从图的结构上考虑一禁用某些特定的子图.即禁用子图条件.设H是一个连通图组成的图类,称图G是H-free的如果对任意的H∈H,G都不含H作为导出子图,此时称H为G的一个禁用子图.K1,3是最常用到的禁用子图之一,K1,3-free图亦称无爪图.1984年Matthews和Sumner提出了下述著名猜想:任意4-连通无爪图都是哈密尔顿图.此后围绕着该猜想,无爪图的哈密尔顿性越来越受到众多图论专家的关注,并且产生了许多有趣的概念、研究方法和技巧。
本论文主要研究了关于3-连通图哈密尔顿性的双禁用子图条件.根据Chen,Egawa,Gould和Saito的一个结果,使3-连通图成为哈密尔顿图的双禁用子图中一定有一个为K1,3或K1,4。
首先考虑将K1,3作为一个禁用子图的情形.设i≥3,定义Pi为恰含i个点的路.设i,j,k为满足i+j+k≥1的非负整数,定义Ni,j,k为将一个三角形的三个顶点分别与长度为i,j,k的三条点不交的路的各一个端点重合所得到的图。Luczak和Pfender证明了任何3-连通{K1,3,P11}-free图是哈密尔顿图;Lai,Xiong,Yan和Yan证明了任何3-连通{K1,3,N8,0,0}-free图是哈密尔顿图.本文证明了任意3-连通{K1,3,Ni,j,k}-free图都是哈密尔顿图,其中i,j,k为任意满足i+j+k=9的正整数.该结论中的常数9是最好可能的,即9不能用更大的数字代替.在第二章中我们论述了主要引理和证明思路.考虑到对称性,满足i+j+k=9的正整数i,j,k的取法共有7种.所以我们根据i,j,k的取值,将7个结论分成三组分别证明.第三章中我们证明任意3-连通{K1,3,N5,2,2}-free图或{K1,3,N4,3,2)-free图是哈密尔顿图.第四章中我们证明任意3-连通{K1,3,Y}-free图是哈密尔顿图,其中Y是N7,1,1,N6,2,1,N5,3,1和N4,4,1中之一.第五章中我们证明任意3-连通{K1,3,N3,3,3}-free图是哈密尔顿图。
其次对于包含K1,4作为一个禁用子图的情形,我们在第六章中证明了任意3-连通{K1,4,P5}-free图都是哈密尔顿图.并由此完全刻画了所有的包含K1,4的双禁用子图:设H是包含至少3个点的连通图,则任意3-连通{K1,4,H}-free图是哈密尔顿图当且仅当H为P3,P4或P5之一.该结果改进了Chen,Egawa,Gould和Saito等人的相关工作。