无爪图的Hamilton性

发布时间：2024-03-13 20:52

　　本文主要研究无爪图在不同子图的度和条件下的路圈性质,Hamilton圈以及Hamilton连通性),得出了无爪图有Hamilton圈和Hamilton路的三个充分条件.第一章我们介绍了图论中Hamilton问题的研究背景和无爪图有Hamilton圈和Hamilton路的现有结果,以及本文中所需用到的的一些基本概念和符号术语.第二章主要讨论无爪图中任意两个不相邻子图在度和条件下的Hamilton圈性质,得到了如下结果:定理2.1设G是n阶3-连通无爪图,如果G中任意两个分别同构于P₄和K₁的不相邻子图H₁和H₂的度和d(H₁)+d(H₂)≥n-2,则G有Hamilton圈.定理2.2设G是n阶3-连通无爪图(n>12),如果G中任意两个分别同构于P₄和K₂的不相邻子图H₁和H₂的度和d(H₁)+d(H₂)≥n-3,则G有H...

【文章页数】：61 页

【学位级别】：硕士

【部分图文】：

图1距离无爪图类禁用子图

令C表示无爪图类,本文研究另一图类———距离无爪图类(DC),称图G∈DC,即对v∈V(G),<Ni(v)>≤2,i≥1.显然DCC.本文还将研究以下禁用子图(如图1).其中(b)图是由F.BRUCESHEPHERD定义的网.即以K3代替K1,3中的顶点,且使K3中的每个顶点....

图2在G[Ti]中构造的P1路

情形2.2.1:令s∈S1,如果d(s)≥3,则s必在最小割集中,因而它必有两个不联接的邻点u,v.令x1,x2∈T2,且x1,x2不邻接,y1,y2∈T1,使得x1y1,x2y2∈E(G).因为G∈C,所以y1≠y2,由于G<x1,x2,y1,y2,u,s,v>不构成Effil....

本文编号：3927555