本文主要研究無爪圖在不同子圖的度和條件下的路圈性質(zhì),Hamilton圈以及Hamilton連通性),得出了無爪圖有Hamilton圈和Hamilton路的三個(gè)充分條件.第一章我們介紹了圖論中Hamilton問題的研究背景和無爪圖有Hamilton圈和Hamilton路的現(xiàn)有結(jié)果,以及本文中所需用到的的一些基本概念和符號(hào)術(shù)語.第二章主要討論無爪圖中任意兩個(gè)不相鄰子圖在度和條件下的Hamilton圈性質(zhì),得到了如下結(jié)果:定理2.1設(shè)G是n階3-連通無爪圖,如果G中任意兩個(gè)分別同構(gòu)于P₄和K₁的不相鄰子圖H₁和H₂的度和d(H₁)+d(H₂)≥n-2,則G有Hamilton圈.定理2.2設(shè)G是n階3-連通無爪圖(n>12),如果G中任意兩個(gè)分別同構(gòu)于P₄和K₂的不相鄰子圖H₁和H₂的度和d(H₁)+d(H₂)≥n-3,則G有H...

【文章頁數(shù)】：61 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖1距離無爪圖類禁用子圖

令C表示無爪圖類,本文研究另一圖類———距離無爪圖類(DC),稱圖G∈DC,即對(duì)v∈V(G),<Ni(v)>≤2,i≥1.顯然DCC.本文還將研究以下禁用子圖(如圖1).其中(b)圖是由F.BRUCESHEPHERD定義的網(wǎng).即以K3代替K1,3中的頂點(diǎn),且使K3中的每個(gè)頂點(diǎn)....

圖2在G[Ti]中構(gòu)造的P1路

情形2.2.1:令s∈S1,如果d(s)≥3,則s必在最小割集中,因而它必有兩個(gè)不聯(lián)接的鄰點(diǎn)u,v.令x1,x2∈T2,且x1,x2不鄰接,y1,y2∈T1,使得x1y1,x2y2∈E(G).因?yàn)镚∈C,所以y1≠y2,由于G<x1,x2,y1,y2,u,s,v>不構(gòu)成Effil....

本文編號(hào)：3927555