雷萬鵬，李 婷，李瑞霖

(1.太原師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，山西 晉中 030619;2.山西工程科技職業(yè)大學(xué) 基礎(chǔ)教學(xué)部，山西 晉中 030619)

1972年，Chvátal和Erd?s[1]利用獨立數(shù)和連通度給出了圖是哈密爾頓的(可跡的，哈密爾頓連通的)一個著名的充分條件.用κ(G)和α(G)分別表示圖G的連通度和獨立數(shù).

定理1(Chvátal和Erd?s)[1]如果G是頂點個數(shù)至少是3的簡單圖，并且滿足α(G)≤κ(G)(α(G)≤κ(G)+1，α(G)≤κ(G)-1)，那么G是哈密爾頓的(可跡的，哈密爾頓連通的).

定理1被延拓至許多不同的方向[2-8].

哈密頓路可以看作是恰好有兩個葉子點的支撐樹.從這個角度上看，一些圖可跡的充分條件可以拓展到至多k個葉子點的支撐樹存在的充分條件.很顯然，如果s≤t，那么一個至多s個葉子點的支撐樹也是至多t個葉子的支撐樹.Win將定理1推廣到至多k個葉子點的支撐樹上.

定理2(Win)[9]令k≥2且G是連通簡單圖.如果α(G)≤κ(G)+k-1，那么G中有一個至多k個葉子點的支撐樹.

從一般意義上來講，獨立數(shù)反映了圖的稀疏程度，而連通度反映了圖的密集程度.而實際上，獨立數(shù)作為圖的一個參數(shù)，并不能反映圖在整體意義上的稀疏程度，它只是一個圖的局部范圍內(nèi)的指標(biāo).為了能更準(zhǔn)確地反映圖的稀疏程度，Chen[10]等引入了最大獨立集個數(shù)這個指標(biāo)，令m(H)為圖G的子圖H的最大獨立集的個數(shù).并且證明了當(dāng)限制m(H)的范圍時，G的獨立數(shù)稍微擴大一點(即α(G)≤κ(G)+2)不會改變其可跡性.

定理3(Chen等)[10]設(shè)G為n≥2κ2(G)的2-連通圖.如果κ(G)=κ，α(G)≤κ+2.并且m(G)≤n-2κ-1，那么要么G是可跡的，要么G屬于某一類反例圖.

Lei等[11]將Chen等的結(jié)論拓展到了至多k個葉子點的支撐樹上，Lei等推廣了Win定理并得到以下結(jié)果.

定理4(Lei等)[11]令k≥2且G是一個n≥2k+2的連通簡單圖.如果α(G)≤1+k并且m(G)≤n-2k-2，那么G中有至多k個葉子點的支撐樹.

然而，定理4中m(G)的界并不是緊的.本文主要研究了基于最大獨立集個數(shù)的至多3個葉子點支撐樹的存在性問題，并得到了m(G)的界是最好可能的.為了證明主要結(jié)論，利用如下引理.

引理5[11]假設(shè)X是G中最大的一個獨立集.令S?V(G)使得|S∩X|=1，設(shè){z}=S∩X.如果對任意的x∈z}，N(x)∩X={z}都成立，那么G[S]是一個團.

假設(shè)S是G中一個子圖，令c(G-S)為G-S的分支個數(shù).下面是本文主要結(jié)論：

定理6令G是一個簡單圖，P是G中一條最長路.如果α(G)≤κ(G)+3，c(G-P)≥2，m(G)≤n-2κ(G)-3并且G-P的每一個分支在P中鄰點相同，那么G中包含一個至多3個葉子點的支撐樹.

注：由定理2可知，定理4中圖G的連通度為1.由此可見，本文結(jié)論中最大獨立集的個數(shù)的界比定理4中的界要好，并且是最好可能的，對于連通度也沒有任何限制.

1 符號與術(shù)語

2 定理6的證明

證明 假設(shè)G中不包含一個至多3個葉子點的支撐樹，則G中沒有哈密爾頓路，故P不是哈密爾頓路.令aP和bP為P的兩個端點.對P從aP到bP定向，因此，對于V(P)中的每一個內(nèi)部頂點x，定義x+，x-.對于P中任給的頂點x,y，P[x,y]指由P中連續(xù)頂點構(gòu)成的一條路xx+x2+…xs+(=y).

因為P是G中的一條最長路，所以很容易驗證aP，bP?U,并且下列{ν,aP}∪U+和{ν,bP}∪U-是G中的兩個獨立集.又因為c(G-P)≥2，不妨令ν∈V(D1)，ω∈V(D2)，D1，D2分別為G-P的兩個不同的分支.

則{ν,ω,aP}∪U+和{ν,ω,bP}∪U-是獨立數(shù)為κ+3的G中的兩個獨立集.令X={ν,ω,aP}∪U+，Y={ν,ω,bP}∪U-，則c(G-P)=2，否則與獨立數(shù)κ+3矛盾.

斷言1D1，D2都是一個團.

證明 由對稱性，只考慮D1即可.由分支的定義，僅考慮|V(D1)|>2.假設(shè)任意取兩點v1,v2∈V(D1)且v1v2?E(G).

如果viaP∈E(G)(i=1,2)，那么viP是一條比P長的路，與P是G中最長路相矛盾.故viaP?E(G)(i=1，2)，同理vibP?E(G)(i=1,2).

如果v1v2?E(G)，{ω,v1,v2,aP}∪U+是G中的獨立集，則獨立數(shù)為κ(G)+4與κ(G)+3矛盾，故v1v2∈E(G)，由v1,v2∈V(D1)的任意性，D1是團.證畢.

圖1

圖2

圖3

圖4

圖5

圖6

圖7

圖8

圖9

圖10

圖11

圖12

圖13

由斷言1,2和4，很容易驗證：

斷言5c(G-U)=κ+3，即任意兩個團Ai均互不相鄰.