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

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

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

V(H)?V(P)

或者:

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

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

(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時(shí)，去掉路P上的U0,然后再增加一條從p1出發(fā)且與Fp相連的路，從而獲得一條新路記作P0。分2種情況來(lái)討論：

情況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的交集之中存在一個(gè)頂點(diǎn)在路P0之外，因此有：

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

這與條件(2)相矛盾。

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

情況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的交集之中存在一個(gè)頂點(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的交集之中存在一個(gè)頂點(diǎn)在Pi之外，因此有：

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

這與條件(2)相矛盾。

綜上所述，論斷1成立。

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

有：

即：

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

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

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

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

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

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

情況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的交集之中存在一個(gè)頂點(diǎn)在P′之外，因此有：

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

這與條件(2)相矛盾。

通過(guò)對(duì)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)樹(shù)的獨(dú)立數(shù)條件的證明

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

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

α(G)≤n+k-1

則G中存在一個(gè)支撐樹(shù)T使得：

|Leaf(T)|≤k

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

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

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

然后，在G中選取一個(gè)支撐樹(shù)T滿足以下2個(gè)條件:

(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路上與一個(gè)度大于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é)語(yǔ)

研究了n-連通圖中存在包含給定頂點(diǎn)的路的條件，應(yīng)用這一結(jié)論證明了n-連通圖中支撐k-端點(diǎn)樹(shù)存在的獨(dú)立數(shù)條件。該結(jié)論在圖的支撐樹(shù)研究中有著重要的意義，對(duì)于論證其他關(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.