圖的連通度與其路圈可擴(kuò)性.pdf

1、路和圈是圖的兩個基本結(jié)構(gòu),是分析、刻畫圖的整體結(jié)構(gòu)的有力工具.大量的實(shí)際問題都可以歸結(jié)為圖的路圈問題.圖論問題中三大著名難題之一hamilton問題本質(zhì)上也是圖的路和圈的問題,對圖的路和圈的問題的研究一直是圖論研究中的熱點(diǎn)領(lǐng)域.最近若干年來,關(guān)于這方面的研究主要集中在路圈問題,具體的講主要集中在:hainilton圈,泛圈,點(diǎn)泛圈,圈可擴(kuò),最長圈,hamilton連通,泛連通,laamilton路,路可擴(kuò),最長路等性質(zhì)的研究上,而且取得

2、了長足的發(fā)展.關(guān)于這方面的研究及最新研究參看[2]-[16].對這些性質(zhì)的研究主要集中在兩個方面:一方面是尋求圖的路圈性質(zhì)的充分條件;另一方面是研究某些特殊圖類的路圈性質(zhì). 連通度是圖論中較早提出的一個概念,是刻畫圖的"連通程度"的一個重要指標(biāo).可以想象,當(dāng)一個圖的連通度相對圖的階是較高時,可以保證圖的各種性質(zhì)路圈性質(zhì),隨著連通度逐漸降低,圖的各種性質(zhì)路圈性質(zhì)也將發(fā)生變化乃至消失.連通度應(yīng)滿足什么條件才能保證圖的路圈性質(zhì)呢?因此

3、能夠保證圖具有某種路圈性質(zhì)的連通度的下確界是什么自然就是一個很值得關(guān)注和研究的問題,但是在圖的路圈性質(zhì)的研究中,目前這方面的研究還不多. 為了尋圖的完全圈可擴(kuò)性與連通度的下確界的關(guān)系,2006年劉曉妍研究了連通度為|G|-3,|G|-4,|G|-5的圖G的完全圈可擴(kuò)性,得到了以下結(jié)果: 定理1<'[2]>設(shè)G滿足k(G)=n-3且|G|≥7,則G是完全圈可擴(kuò)的.定理2<'[2]>設(shè)G滿足k(G)=n-4且|G|≥9,則G

4、是完全圈可擴(kuò)的.定理3<'[2]>設(shè)G滿足k(G)=n-5且|G|≥11,則G是完全圈可擴(kuò)的.根據(jù)以上三個結(jié)果反映出來的規(guī)律,劉曉妍提出如下猜想:猜想1若G滿足k(G)=|G|-s+1且|G|≥2s-1,則G是完全圈可擴(kuò)的.并且說明了如果猜想1成立, 則其中的連通度的下界是最好可能的,并進(jìn)一步得到了定理5.本文延續(xù)了劉曉妍思路,做了兩方面的工作.首先證明了劉曉妍提出的猜想,(不妨把猜想1稱為定理4),定理5. 此猜想顯然包含了定

5、理4,并且說明了如果猜想成立,那么其中連通度下界是最好可能的. 遺憾的是在嘗試了對猜想2,猜想3證明的過程中,在一些特定的情況下遇到了一定的困難,由于時間的原因,在本文完成之前,證明還未完全做出. 本文分為兩章.在第一章中,主要介紹了論文中所涉及到的一些概念、術(shù)語、符號、本文的研究背景及已有的研究結(jié)果.在第二章中,研究了連通度與完全圈可擴(kuò)、路可擴(kuò)之間的聯(lián)系,主要證明了引理2,引理3,定理4,定理5,定理6,定理7,定理8