本文關(guān)鍵詞：圖的路圈性質(zhì)及連通性的研究

  更多相關(guān)文章： Homilton Dominating 路 圈 [s t]-圖 2-因子

【摘要】：圖論是現(xiàn)代數(shù)學(xué)的重要分支之一,圖的路、圈問題又是圖論中一個十分重要而且活躍的研究課題,大量的實(shí)際問題可以歸結(jié)為路和圈的問題.事實(shí)上,圖論中三大著名難題之一的Hamilton問題本質(zhì)上也是圖的路和圈問題.這方面的研究成果和進(jìn)展可參見文獻(xiàn)[29]-[33].由于直接研究一般圖的Hamilton問題往往比較困難,于是人們轉(zhuǎn)而研究不含有某些禁用子圖的圖類,如無爪圖.繼Beineke1970年發(fā)表的關(guān)于線圖性質(zhì)的文章[11]-[12]之后,人們開始關(guān)注包含著線圖的無爪圖.70年代末80年代初,是研究無爪圖的一個非�；钴S的時期.關(guān)于無爪圖方面的部分優(yōu)秀成果可參考[13]-[28].如果圖G中任意s個頂點(diǎn)之間至少存在t條邊,則稱G是[s,t]-圖.這一概念是劉春房,王江魯2005年在[2]中給出的.由于”α(G)≤k當(dāng)且僅當(dāng)G是[k+1,1]-圖(這里a(G)是圖G的點(diǎn)獨(dú)立數(shù))”[3],所以從某種意義上講[s,t]-圖是圖的獨(dú)立數(shù)概念的推廣.此外,易舉出大量實(shí)例,其中所包含的問題可以歸結(jié)為對[s,t]-圖的研究.比如在染色,交通網(wǎng)絡(luò),通信系統(tǒng),計(jì)算機(jī)的網(wǎng)絡(luò)配置等方面.目前,對[s,t]-圖的研究都集中在其路、圈性質(zhì)的研究上,已有的研究成果大都是對[s,t]-圖中s,t是一些較小的正整數(shù)的研究.第一個具有一般意義的研究成果是王江魯,牟磊在[3]中給出的下邊的兩個結(jié)果：(1)若圖G是k-連通[k+2,2]-圖,則G或者含有Hamilton圈或者同構(gòu)于Petersen圖或者同構(gòu)于Kk+2∨Gk.(這里Gk是含有k個頂點(diǎn)的任意圖,下同)(2)若圖G是k-連通[k+3,2]-圖(k≥2),則G或者含有Hamilton路或者同構(gòu)于Kk+2∨Gk.由這兩個結(jié)果可以分別推得Chvatal-Erdos和Bondy用點(diǎn)獨(dú)立數(shù)α(G)和連通度k(G)給出的下述經(jīng)典結(jié)果：(a) (Chvatal-Erdos and Bondy[6])設(shè)圖G的階n≥3,如果α(G)≤κ(G),則G含有Hamilton圈.(b)(Bondy [7])設(shè)圖G的階n≥3,如果α(G)≤κ(G)+1,則G含有Hamilton路.在[6]中Chvatal-Erdos還給出了另一個經(jīng)典結(jié)果：定理[6]設(shè)圖G的階n≥3,如果α(G)≤κ(G)-1,則G是Hamilton連通的.在本文的第二章將給出它的推廣：定理若圖G是k-連通[k+1,2]圖,則G或者是Hamilton連通的或者同構(gòu)于KK∨Gk.鑒于目前對[s,t]-圖的研究還處于初級階段,本文繼續(xù)了[s,t]-圖路圈性質(zhì)的研究.在第一章中,主要介紹文章中所涉及的一些概念和術(shù)語符號,以及本文的研究背景和已有的一些結(jié)果.在第二章中,主要研究了[s,t]-圖在不同條件下的Hamilton連通性質(zhì),得到下面的結(jié)果：定理2.1.1若圖G是k-連通[k+1,2]-圖(k≥2),則G或者是Hamilton連通的或者同構(gòu)于Kk∨Gk.推論2.1.1設(shè)G是n(≥3)階,k-連通[k+1,2]-圖且|G}≥2k+1,則G是Hamilton連通的.推論2.1.2設(shè)G是n(≥3)階δ≥k+l,k-連通[k+1,2]圖,則G為Hamilton連通.推論2.1.3設(shè)G是n(≥3)階,α(G)≤k-1,則G為Hamilton連通.定理2.1.2若圖G是δ≥k+1,k-連通[k+2,3]-圖(k≥2),則G或者是Hamilton連通的或者同構(gòu)于Kk+1∨Gk+1推論2.1.4 設(shè)G是n(≥3)階,δ≥k+1,k-連通[k+2,3]圖且|G|≥2k+3,則G是Hamilton連通的.推論2.1.5設(shè)G是n(≥3)階,δ≥k+2,k-連通[k+2,3]-圖,則G為Hamilton連通.在第三章中,討論了在|Nc(B)|≥k(|NP(B)|≥k)的條件下[s,t]-圖的Hamilton的路圈性質(zhì),得到下面的結(jié)果：定理3.1.1設(shè)圖G是[k+3,2]-圖(k≥2)且不含Hamilton路,P是G的一條最長路,如果對G-V(P)的任一分支B有|NP(B)|≥k,則G同構(gòu)于Kk+2∨Gk.推論3.1.1若圖G是k-連通[k+3,2]-圖,則G或者含有Hamilton路或者同構(gòu)于瓦Kk+2∨Gk.定理3.1.2設(shè)圖G是δ≥k+1,[k+4,3]-圖(k≥2)且不含Hamilton路,P是G的一條最長路,如果對G-V(P)的任一分支B有|NP(B)|≥k,則G同構(gòu)于Kk+3∨Gk+1.推論3.1.2若G是δ≥k+1的k-連通[k+4,3]-圖,則G有Hamilton路或G同構(gòu)于Kk+3∨ Gk+1.定理3.1.3設(shè)圖G是[k+2,2]-圖(k≥2)且不含Hamilton圈,C是G的一條最長圈,如果對G-V(C)的任一分支B有|NC(B)|≥k,則G或者同構(gòu)于Petersen圖或者同構(gòu)于Kk+1∨Gk推論3.1.3若圖G是k-連通[k+2,2]-圖,則G或者含有Hamilton圈或者同構(gòu)于Petersen圖或者同構(gòu)于Kk+1∨ Gk.定理3.1.4設(shè)圖G是[k+1,2]-圖(k≥2)且不是Hamilton連通的,P是G的一條最長路,如果對G-V(P)的任一分支B有|NP(B)|≥k,則G同構(gòu)于Kk∨Gk.定理3.1.5設(shè)圖G是δ≥k+1,[k+2,3]-圖(k≥2)且不是Hamilton連通的,P是G的一條最長路,如果對G-V(P)的任一分支B有|NP(B)|≥k,則G同構(gòu)于Kk+1∨Gk+1.定理3.2.1設(shè)圖G是δ(G)≥3,[4,2]-圖且不含Hamilton圈,G是G的一條最長圈如果對G-V(C)的任一分支B有|NC(B)|≥1,則G有2-因子.推論3.2.1設(shè)圖G是連通[4,2]-圖,若δ(G)≥3,則G有2-因子.定理3.2.2設(shè)圖G的階為n(n≥5),是[k+2,1]-圖(k≥2)且不含Hamilton圈,C是G一條最長圈如果對G-V(C)的任一分支B有|NC(B)|≥k,則G有2-因子.推論3.2.2[10]設(shè)圖G是n(n≥5)階k-連通[k+2,1]-圖,則G有2-因子.在第四章中,涉及的是[s,t]-圖的Dominating性質(zhì),得到下面的結(jié)果：定理4.1.1若圖G是k-連通[k+3,3]-圖(k≥2),則G含有Dominating圈.定理4.2.1若圖G是k二連通[k+4,3]-圖(k≥2),則G含有Dominating路
【學(xué)位授予單位】：山東師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5

【參考文獻(xiàn)】

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 程建民;圖中強(qiáng)路圈性質(zhì)的若干充分條件[D];山東師范大學(xué);2009年

，

本文編號：1213104