若干圖類的路和圈問題.pdf

1、路和圈是圖的兩種基本結(jié)構(gòu)，是分析和刻畫圖的有力工具，有大量的實(shí)際問題可以歸結(jié)為圖的路和圈問題，所以這方面一直是圖論中的熱點(diǎn)研究領(lǐng)域.事實(shí)上，圖論中三大著名難題之一的Hamilton問題本質(zhì)上也是圖的路和圈問題.最近若干年來，這方面的研究主要集中在圖的Hamilton性，泛圈，點(diǎn)泛圈，圈可擴(kuò)，最長圈，Hamilton連通，路可擴(kuò)，最長路等性質(zhì)的研究上而且已經(jīng)取得了長足的進(jìn)展.由于直接研究一般圖的Hamilton問題往往比較困難，于是人們轉(zhuǎn)

2、而研究不含有某些禁用子圖的圖類.繼Beineke1968，1970年發(fā)表的關(guān)于線圖性質(zhì)的兩篇文章[17]-[18]之后，人們開始關(guān)注包含著線圖的無爪圖.70年代末80年代初，是研究無爪圖的一個(gè)非常活躍的時(shí)期.關(guān)于無爪圖方面的部分優(yōu)秀成果可參考[2]-[4]，[19]-[33].[34]是關(guān)于無爪圖的綜述性的文章.另外，無爪圖的概念也被從不同角度推廣到了更大的圖類，如半無爪圖，幾乎無爪圖，(K1，4；2)-圖，DCT圖等.1998年，A.

3、Ainouche在[7]中定義了一種包含無爪圖的更大的圖類-半無爪圖且給出了關(guān)于半無爪圖的路和圈方面的一些結(jié)果.之后，很多專家學(xué)者相繼做了大量工作來研究這類圖的Hamilton問題且將無爪圖中的許多非常好的結(jié)果推廣到了半無爪圖.其中，某些進(jìn)展可參考[35]-[37].1994年，Z.Ryjácek[38]定義了一種包含無爪圖的更大的圖類-幾乎無爪圖.之后，亦出現(xiàn)了不少研究這類圖的Hamilton問題的學(xué)術(shù)論文如[39]-[41].但事實(shí)

4、上，無爪圖中許多很好的結(jié)果要推廣到幾乎無爪圖難度非常大.所以，滕延燕，尤海燕2003年[5]在此基礎(chǔ)上提出了擬無爪圖的概念，它包含無爪圖類但卻包含在幾乎無爪圖類中.但是，在這個(gè)概念下，很多至今還沒有能夠推廣到幾乎無爪圖的無爪圖中的非常好的結(jié)果卻可以推廣到擬無爪圖.K1,p-擴(kuò)展圖是我們在研究不同圖類結(jié)構(gòu)的基礎(chǔ)上所提出的一種包含K1,p+1-free圖的新的圖類.(A)獨(dú)立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)

5、∩N(x2)∩…N(xp)≠φ，那么若(A)u∈N(x1)∩N(x2)∩…N(xp)，有N[u](∈)N[x1]∪N[x2]∪…∪N[xp]，則稱u為{x1，x2，…，xp}的控制點(diǎn).否則，稱u為{x1，x2，…，xp}的非控制點(diǎn).將{x1，x2，…，xp}的控制點(diǎn)組成的集合稱為{x1，x2，…，xp}的控制集，記為D(x1，x2，…，xp)；{x1，x2，…，xp}的非控制點(diǎn)組成的集合稱為{x1，x2，…，xp}的非控制集，記為：D(

6、x1，x2，…，xp).(A)獨(dú)立集{x1，x2，…，xp}(∈)V(G)(p≥2)，如果N(x1)∩N(x2)∩…N(xp)≠φ，那么D(x1,x2，…，xp)≠φ，且若(A)u∈D(x1，x2，…，xp)，(A)v∈-D(x1，x2，…，xp)，有uv∈E(G)，則稱G為K1,p-擴(kuò)展圖.特別地,K1,2-擴(kuò)展圖類是包含著無爪圖類且比無爪圖類更大的圖類.本篇論文主要研究了無爪圖，半無爪圖，擬無爪圖，K1,p-擴(kuò)展圖的路和圈問題.

7、 在第一章中，我們主要介紹了文章中所涉及的一些概念，術(shù)語符號和本文的研究背景以及已有的一些結(jié)果. 在第二章中，我們通過具體實(shí)例討論了關(guān)于無爪圖的已有的在不同連通條件下的幾個(gè)結(jié)果間的關(guān)系，證明了下面的結(jié)果： 定理2.5無孤立點(diǎn)的三角連通的無爪圖也是半局部連通的. 推論2.6”邊數(shù)不小于3的三角連通的無爪圖是點(diǎn)泛圈的”這個(gè)結(jié)果包含在”頂點(diǎn)數(shù)不小于3的半局部連通的無爪圖是點(diǎn)泛圈的”這個(gè)結(jié)果中. 在第三章中，

8、我們探討了半無爪圖的最長路，點(diǎn)泛圈性以及閉包等問題，進(jìn)一步改進(jìn)了M.Malthews,P.Sumner,R.J.Faudree，HongjianLai,C.Q.Zhang等人的相應(yīng)結(jié)果. 定理3.1.3連通半無爪圖G有Hamilton路或有長至少為2δ(G)+2的路. 定理3.1.4設(shè)G為連通半無爪圖，若δ(G)≥(|G|-2)/3，則G有Hamilton路. 定理3.4.2邊數(shù)不小于3無孤立點(diǎn)的三角連通半無爪圖

9、是點(diǎn)泛圈的. 定理3.5.4頂點(diǎn)數(shù)不小于3的半局部連通的半無爪圖是點(diǎn)泛圈的. 定理3.5.5設(shè)G是連通度κ(G)≥2的半無爪圖，M(G)={x∈V(G)：〈N(x)〉連通}，M(G)是G的控制集且〈M(G)〉有r個(gè)連通分支，若r≤κ(G)，則G是Hamilton圖.其中κ(G)的下界r是最好可能的且G不一定是泛圈的. 定理3.6.1頂點(diǎn)數(shù)不小于3的連通幾乎局部連通半無爪圖G若滿足δ(G)≥3，則G是點(diǎn)泛圈的且其中

10、δ(G)的下界是最好可能的. 定理3.7.1若G是半無爪圖，x是G的一適宜點(diǎn)，G'為由G在x局部完備所得，則G'仍是半無爪圖，但G'不一定是無爪圖. 推論3.7.2若G是半無爪圖，則cl(G)是半無爪圖. 定理3.7.3若G是半無爪圖，則cl(G)是唯一確定的. 在第四章中，我們研究了擬無爪圖的最長路，完全圈可擴(kuò)性以及點(diǎn)可排序泛圈性(vertexpancyclicorderable)，進(jìn)一步推廣了R.J.

11、Faudree，R.J.Gould等人的相應(yīng)結(jié)果. 定理4.1.2連通擬無爪圖G有Hamilton路或有長至少為2δ(G)+2的路. 定理4.1.3設(shè)G為連通擬無爪圖，若δ(G)≥(|G|-2)/3，則G有Hamilton路. 定理4.1.4設(shè)G為n階2-連通擬無爪圖，若NC≥(n-2)/2，則G有Hamilton路. 定理4.2.4無孤立點(diǎn)的三角連通的擬無爪圖是完全圈可擴(kuò)的也是點(diǎn)可排序泛圈的(verte