基于最大獨(dú)立集個(gè)數(shù)下的至多3個(gè)葉子點(diǎn)支撐樹的存在性

雷萬鵬，李 婷，李瑞霖

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

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

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

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

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

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

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

定理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個(gè)葉子點(diǎn)的支撐樹上，Lei等推廣了Win定理并得到以下結(jié)果.

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

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

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

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

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

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

1 符號(hào)與術(shù)語

2 定理6的證明

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

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

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

斷言1D1，D2都是一個(gè)團(tuán).

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

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

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

圖1

圖2

圖3

圖4

圖5

圖6

圖7

圖8

圖9

圖10

圖11

圖12

圖13

由斷言1,2和4，很容易驗(yàn)證：

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