n-連通圖的支撐k-端點(diǎn)樹

嚴(yán)政，方志軍，劉敏(長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

如果圖中存在通過圖中的每個頂點(diǎn)一次且僅一次的回路(路)，則稱圖中存在哈密爾頓通圈(路)。研究圖中存在哈密爾頓圈(路)的問題是結(jié)構(gòu)圖論中重要的研究方向。一般地，尋找一個圖的哈密頓圈(路)問題是NP困難的。1960年，Ore[1]給出了圖中存在哈密爾頓圈的充分條件：對于任意頂點(diǎn)個數(shù)大于2的圖，如果圖中任意不相鄰兩點(diǎn)度的和大于或等于頂點(diǎn)總數(shù)，則這個圖一定存在哈密爾頓圖；1972年，Chvtal和Erd?s[2]獲得了圖中存在哈密爾頓圈的獨(dú)立數(shù)條件：對于任意頂點(diǎn)個數(shù)大于2的連通圖，如果圖獨(dú)立頂點(diǎn)數(shù)目小于或等于圖的連通度，則這個圖一定存在哈密爾頓圖。這2個條件是圖中存在哈密爾頓圈的經(jīng)典結(jié)論。一個圖存在哈密爾頓路，說明該圖存在只含2個葉子的支撐樹或最大度等于2的支撐樹。路作為一類最簡單的樹，自然就會引申出如下的問題：對于任意正整數(shù)k，如何保證圖存在最大度不超過k的支撐樹即支撐k-樹,或圖中存在至多k個葉子的支撐樹即支撐k-端點(diǎn)樹等一系列問題。下面，筆者研究了n-連通圖中存在包含給定頂點(diǎn)的路的條件，并應(yīng)用這一結(jié)論證明了n-連通圖中存在支撐k-端點(diǎn)樹的獨(dú)立數(shù)條件。其中，符號及術(shù)語參見文獻(xiàn)[3]。

1 包含給定頂點(diǎn)的路的n-連通圖條件

1994年，Kouider[4]研究了n-連通圖中存在包含給定子圖的圈的條件。2011年，Suil等[5]獲得了n-連通圖中存在給定端點(diǎn)的路的獨(dú)立數(shù)條件。筆者應(yīng)用Suil的方法，給出了如下定理。

定理1設(shè)G是一個n-連通圖，H是G的子圖，則G中存在一條路P，使得：

V(H)?V(P)

或者:

α(H-V(P) )≤α(H)-(n+1)

證明首先，假設(shè)不存在一條路P包含V(H)。對于每一條路P，設(shè)Fp表示G-V(P)中與H相交不為空的最小分支。選取一條路P滿足以下2個條件：

(1)α(H-V(P))最小；

(2)在α(H-V(P))最小的條件下，|FP|最小。

令p0,p1,p2,…,pm，pm+1是路P中按照下標(biāo)順序排列的點(diǎn)，且p1,p2,…,pm與Fp相鄰接,p0,pm+1是路P的兩端點(diǎn)，令：

U0=V(P(p0，p1))Ui=V(P(pi，pi+1)) (0

論斷1α(H-V(P-Ui) )>α(H-V(P)),0≤i≤m。

如果論斷1不成立，則α(H-V(P-Ui) )=α(H-V(P))。

當(dāng)i=0時，去掉路P上的U0,然后再增加一條從p1出發(fā)且與Fp相連的路，從而獲得一條新路記作P0。分2種情況來討論：

情況1 如果V(Fp)與V(H)的交集是V(P0)的子集，那么就有:

α(H-V(P0))<α(H-V(P))

這與條件(1)相互矛盾。

情況2 如果V(Fp)與V(H)的交集不完全包含在V(P0)之中，因?yàn)閂(P-U0)∈V(P0),有:

α(H-V(P0))≤α(H-V(P-U0) )=α(H-V(P))

又因?yàn)樵贔p與H的交集之中存在一個頂點(diǎn)在路P0之外，因此有：

|V(FP0)|<|V(Fp)|

這與條件(2)相矛盾。

當(dāng)i=m時，去掉路P上的Um, 然后再增加一條從pm出發(fā)且與Fp相連的路，形成的新路記作路Pm。分2種情況來討論：

情況3 如果V(Fp)與V(H)的交集是V(Pm)的子集，那么就有:

α(H-V(Pm))<α(H-V(P))

這就與條件(1)相互矛盾。

情況4 如果V(Fp)與V(H)的交集不完全包含在V(Pm)之中，因?yàn)閂(P-Um)∈V(Pm),有：

α(H-V(Pm))≤α(H-V(P-Um) )=α(H-V(P))

又因?yàn)樵贔p與H的交集之中存在一個頂點(diǎn)在Pm之外，因此有：

|V(FPm)|<|V(Fp)|

這與條件(2)相矛盾。

當(dāng)0

情況5 如果V(Fp)與V(H)的交集是V(Pi)的子集，那么就有:

α(H-V(Pi))<α(H-V(P))

這就與條件(1)相互矛盾。

情況6 如果V(Fp)與V(H)的交集不完全包含在V(Pi)之中，因?yàn)閂(P-Ui)∈V(Pi),有：

α(H-V(Pi))≤α(H-V(P-Ui) )=α(H-V(P))

又因?yàn)樵贔p與H的交集之中存在一個頂點(diǎn)在Pi之外，因此有：

|V(FPi)|<|V(Fp)|

這與條件(2)相矛盾。

綜上所述，論斷1成立。

由論斷1可知，重新添加Ui到誘導(dǎo)子圖H-V(P)中，α(H-V(P-Ui) )會變大。顯然Ui是非空的，p0，p1,p2，…，pm，pm+1在路P中兩兩不相鄰,且m≥n。按照順序恢復(fù)Ui中的頂點(diǎn)到H-V(P-Ui)中，以pi為起點(diǎn)，設(shè)qi為第一個使其獨(dú)立數(shù)增加的點(diǎn)。由論斷1知，qi≠pi+1。令:

有：

即：

當(dāng)i≠0,j≠m時，去掉路P的V(P(pi,ri))和V(P(pj,rj))，增加路P*和一條經(jīng)過Fp的(Pi+1，Pj+1)-路，最終形成的新的路稱作Pij。

當(dāng)i=0,j≠m時，去掉路P的V(P(p0,r0))和V(P(pj,rj))，增加路P*和一條以pi為起點(diǎn)連接Fp的路，最終形成的新的路稱作P0j。

當(dāng)i≠0,j=m時，去掉路P的V(P(pi,ri))和V(P(pj,rj))，增加路P*和一條經(jīng)過Fp的(pi，pm)-路，最終形成的新的路稱作Pim。

當(dāng)i=0,j=m時，去掉路P的V(P(p0,r0))和V(P(pm,rm))，增加路P*和一條經(jīng)過Fp的(p1，pm)-路，F(xiàn)p的路，最終形成的新的路稱作P0m。

α(H-V(P′) )≤α(H-V(P))

如在論斷1所證明的一樣，分2種情況來討論。

情況1 如果V(Fp)與V(H)的交集是V(P′)的子集(P′表示Pij、P0j、Pim、P0m)，那么有；

α(H-V(P′))<α(H-V(P))

這就與條件(1)相互矛盾。

情況2 如果V(Fp)與V(H)的交集不完全包含在V(P′)之中，因?yàn)閂(P-Ui)∈V(P′),有：

α(H-V(P′))≤α(H-V(P-Ui) )=α(H-V(P))

又因?yàn)樵贔p與H的交集之中存在一個頂點(diǎn)在P′之外，因此有：

|V(FP′)|<|V(Fp)|

這與條件(2)相矛盾。

通過對qi的選擇，可以得出：

α(H-V(P-U) )≥α(H-V(P) )+m+1

又因?yàn)椋?/p>

α(H)≥α(H-V(P-U) )≥α(H-V(P) )+m+1

且m≥n，故有：

α(H)≥α(H-V(P) )+n+1

即：

α(H)-n-1≥α(H-V(P) )

也即：

α(H-V(P) )≤α(H)-(n+1)

2 支撐k-端點(diǎn)樹的獨(dú)立數(shù)條件的證明

文獻(xiàn)[6]應(yīng)用k-端點(diǎn)系統(tǒng)獲得了定理2，筆者應(yīng)用定理1，給出定理2一個簡短的證明。

定理2設(shè)G是一個n-連通圖，k∈Z，k≥2。如果：

α(G)≤n+k-1

則G中存在一個支撐樹T使得：

|Leaf(T)|≤k

證明若G中存在一條哈密爾頓路，則定理2成立。若G中不存在哈密爾頓路，由定理1，在G中選取一條路P，滿足以下2個條件：

(p1)：α(G-V(P) )≤α(G)-(n+1);

(p2)：在(p1)的條件下，P盡可能的長。

然后，在G中選取一個支撐樹T滿足以下2個條件:

(T1):P是T的子圖，即T包含路P;

(T2):|Leaf(T)|盡可能的小。

論斷3設(shè)路P的端點(diǎn)為x1，x2, 則x1，x2∈Leaf(T)。

假設(shè)xi(i=1,2)不屬于Leaf(T)，則在T中存在y使得xi與y相鄰(xiy∈E(T)),則P″=P+xiy。顯然P″滿足條件(p1)，但是|P″|>|P|，與條件(p2)矛盾，故假設(shè)不成立，即論斷3得證。

論斷4令Leaf(T)={x1，x2，…,xl}，l>2，Leaf(T)是獨(dú)立集。

假設(shè)Leaf(T)不是獨(dú)立集，則存在xi，xj，1≤i，j≤l，使得：

xixj∈E(G)

令：

T′=T+xixj-e

其中，e是xiTxj路上與一個度大于2的點(diǎn)相鄰且不在路P上的邊。顯然：

|Leaf(T′) |=|Leaf(T) |-1

這與條件(T2)矛盾，故假設(shè)不成立，即Leaf(T)是獨(dú)立集。

由于{x3，x4，…,xl}是V(G)-V(P)的子集，由論斷2：

l-2=|{x3，x4，…,xl}|≤α(G-V(P) )

由條件(p1)及定理2的條件，可得：

α(G-V(P) )≤α(G)-(n+1)≤k-2

綜上所述，得：

l-2≤k-2

即：

l≤k

3 結(jié)語

研究了n-連通圖中存在包含給定頂點(diǎn)的路的條件，應(yīng)用這一結(jié)論證明了n-連通圖中支撐k-端點(diǎn)樹存在的獨(dú)立數(shù)條件。該結(jié)論在圖的支撐樹研究中有著重要的意義，對于論證其他關(guān)于獨(dú)立數(shù)條件也很有效[7,8]。

[參考文獻(xiàn)]

[1]Ore O. Note on Hamilton circuits[J]. Amer Math Monthly, 1960, 67: 55.

[3] Bondy J， Murty U S R. Graph theory with applications[M]. London: Macmillan, 1976.

[4] Kouider M. Cycles in graph with prescribed stability number and connectivity[J]. J Combin Theory Ser B, 1994, 60:315～318.

[5] Suil O, West D B, Wu H. Longest cycles ink-connected graphs with given independence number[J]. J Combin Theory Ser B,2011,101:480～485.

[6] Win S. On a conjecture of Las Vergnas concerning certain spanning trees in graphs[J]. Resulate Math, 1979，2:215～224.

[7] Yan Zheng. Independence number andk-trees of graph[J]. Graphs and Combinatorics, 2015,31:1883～1887.

[8] Kano M, Yan Zheng. Spanning trees with bounded degrees and leaves[J]. Discrete Mathematic, 2016，339：1583～1586.