具有3-部極小公平劃分的樹

孫德榮

（昌吉學(xué)院數(shù)學(xué)系 新疆 昌吉 831100）

1 引言

本文考慮的都是簡單無向圖.通常用A=A(G)表示圖G鄰接矩陣，如果圖G有n個(gè)頂點(diǎn)，V={v1,v2,…,vn} 表示圖G的頂點(diǎn)集.如果 π=(C1,C2,…,Ck)是頂點(diǎn)集 V（G）的一個(gè)剖分,即V(G)=C1?C2?…?Ck,且Ci?Cj=φ(i≠j,1≤i,j≤k)，這里Ci稱為劃分π的一個(gè)單元.對任意v∈Ci(1≤i≤k)，用NCj(v)={u∈Cj|uv∈E(G)}表示v在Cj中的鄰點(diǎn)集，如果對Ci(1≤i≤k)中的任意頂點(diǎn)v，dij(v)=|NCj(v)|是常數(shù)（Cj中的點(diǎn)對Ci中的任意頂點(diǎn)v的度的貢獻(xiàn)）,則稱π=(C1,C2,…,Ck)是圖G的一個(gè)k-部公平劃分,每個(gè)圖都至少存在一個(gè)k-部公平劃分，事實(shí)上，如果V(G)=(v1,v2,…,vn)是圖G的頂點(diǎn)集，那么令Ci={Vi}(1≤i≤n)，顯然π=(C1,C2,…,Cn)是圖G的n-部公平劃分，一般來說，一個(gè)圖的公平劃分是不唯一的，例如，圖1

令C1={v1,v5}，C2={v2,v6}，C3={v3,v8}，C4={v4,v7}，容易驗(yàn)證π=(C1,C2,C3,C4)與π′=(C1,C2,C3?C4)都是圖1的公平劃分。圖的公平劃分在圖的結(jié)構(gòu)的研究中有著廣泛的應(yīng)用，我們知道圖的特征值是圖的不變量，它是刻畫圖的特征的一個(gè)重要指標(biāo)。如果圖G的特征值入對應(yīng)的某個(gè)特征向量的分量和不為零，則入稱為圖G的主特征值。而圖的主特征值是圖的閉道數(shù)的主要參數(shù)，與圖的結(jié)構(gòu)有很大的關(guān)系,例如，只有一個(gè)主特征值的圖G一定是正則圖（［1］），這類圖具有1-部公平劃分。Y.Hou和H.Zhou（［2］）找到了所有的恰有兩個(gè)主特征值的樹，分別是：調(diào)和樹Ta(a≥2)、星S1,n和雙星Sn+1,n+1，Y.Hou和F.Tian（［3］）還證明了恰有兩個(gè)主特征值的所有單圈圖是Clk，而這些圖除了調(diào)和樹Ta(a≥2)以外都恰好具有2-部公平劃分。孫德榮（［4］-［5］）證明了頂點(diǎn)集具有二部公平劃分的圖都恰好有兩個(gè)主特征值，并且通過對某些具有3-部公平劃分的樹的研究發(fā)現(xiàn)，這些樹又都恰好有三個(gè)主特征值，而Hagos（［6］）證明了一個(gè)圖G的主特征值的個(gè)數(shù)m(G)等于G的walk-矩陣W(G)的秩，于是孫德榮（［5］）將Hagos的結(jié)論做了進(jìn)一步推進(jìn)，利用公平劃分將圖G的walk-矩陣W(G)進(jìn)行了簡化，給出了關(guān)于圖的公平劃分π的walk-矩陣W(π)并證明了矩陣W(G)的秩=矩陣W(π)的秩=m(G)。本文研究具有3-部公平劃分的樹的結(jié)構(gòu)特征，并給出所有具有3-部公平劃分的樹類。

2 具有3-部極小公平劃分的樹

對于圖G的公平劃分π=(C1,C2,…,Ck)來說，同一個(gè)單元中的點(diǎn)的度是相等的，為敘述方便，我們用d1,d2,…,dk表示相應(yīng)單元的度序列。

如果π=(C1,C2,…,Ck)是圖G的k-部公平劃分，而對任意正整數(shù)j＜k，G的j-部劃分π′=(,,…,)都不是公平劃分，那么 π=(C1,C2,…,Ck)稱為圖G的極小公平劃分。

關(guān)于圖的極小公平劃分有以下基本結(jié)論

定理2.1設(shè)π=(C1,C2,…,Ck)是圖G的k-部公平劃分，d1,d2,…,dk表示相應(yīng)單元的度序列，如果d1,d2,…,dk兩兩不相等，則π一定是圖G的極小公平劃分。

證明：假設(shè)π=(C1,C2,…,Ck)不是圖G的極小公平劃分,則G就存在另外一個(gè)公平劃分π′=（,,…,）是它的極小劃分,其中j＜k.不妨設(shè),…表示這個(gè)極小劃分的度序列,由于d1,d2,…,dk和,,…分別表示同一個(gè)圖的不同劃分的度序列，所以對任意dl(1≤i≤k),存在(1≤m≤j)使得dl=dm′.由于d1,d2,…,dk兩兩不相等,那么…,也應(yīng)兩兩不相等,于是k=j,矛盾。證畢

定理2.2設(shè)π=(C1,C2,…,Ck)是圖G的k-部公平劃分，d1,d2,…,dk表示相應(yīng)單元的度序列。π是圖G的極小公平劃分的充要條件是：對任意di=dj(i≠j)，至少存在一個(gè)單元Cm(1≤m≤k)使得dim(vi)≠djm(vj)(vi∈Ci,vj∈Cj)。

證明：必要性 π=(C1,C2,…,Ck)是圖G的極小公平劃分,若存在di=dj(i＜j),對任意一個(gè)單元Cm(1≤m≤k)都有dim(vi)=djm(vj)(vi∈Ci,vj∈Cj),這樣就可以將劃分π中的單元Ci與Cj合并成一個(gè)單元Ci′=Ci?Cj,而其余單元保持不變,于是就得到圖G的一個(gè)新的公平劃分π′=（C1,C2,…,Ci-1,,Ci+1,…CJ-1,CJ+1,…,Ck）,公平劃分 π′較 π 少了一個(gè)單元,此與 π=(C1,C2,…,Ck)是圖G的極小公平劃分矛盾。

充分性反證法,設(shè)π=(C1,C2,…,Ck)是圖G的k-部公平劃分，d1,d2,…,dk為相應(yīng)單元的度序列,假設(shè)π=(C1,C2,…,Ck)不是圖G的極小公平劃分,那么另存在圖G的一個(gè)極小公平劃分π′=（,,…,）,使得l＜k,這樣就至少存在劃分π的兩個(gè)單元Ci與Cj,當(dāng)di=dj(i≠j)時(shí),單元Ci與Cj中的頂點(diǎn)同屬于π′的某個(gè)單元。由于對任意di=dj(i≠j)，至少存在劃分π一個(gè)單元Cm(1≤m≤k)使得dim(vi)≠djm(vj)(vi∈Ci,vj∈Cj),所以不論Cm(1≤m≤k)中的點(diǎn)屬于劃分π′的哪一個(gè)單元,都不能保證單元中所有的點(diǎn)在劃分π′的其它單元中有相同個(gè)數(shù)的鄰點(diǎn),此與π′是公平劃分矛盾。證畢下面構(gòu)造幾個(gè)具有3-部極小公平劃分的樹，由于星圖S1,n、雙星圖Sn+1,n+1分別是具有2-部公平劃分的樹，在此基礎(chǔ)上，可以構(gòu)造出幾類具有3-部公平劃分的樹。如上圖，在星圖S1,n（圖2.1）的每個(gè)葉子上都懸掛k個(gè)懸掛點(diǎn)得到的新圖（圖2.2）記為。顯然圖是一棵樹。

如上圖，在雙星圖Sn+1,n+1（圖2.3）的每個(gè)懸掛點(diǎn)上都連接k個(gè)懸掛點(diǎn)得到的新圖（圖2.4）記為+1,n+1，顯然圖+1,n+1是一棵樹。

定理2.3樹和1,n+1都具有3-部極小公平劃分。證明：首先證明樹具有3-極小公平劃分，如圖2.2令C1={a1,a2,…,ak,b1,b2,…,bk,…,c1,c2,…,ck} ，C2={v1,v2,…,vn} ，C3={u} ，由定理2.2知，π=(C1,C2,C3)是圖的一個(gè)3-部極小公平劃分。

其次證明樹+1,n+1具有3-極小公平劃分，如圖2.4，令C1={u,v}，C2={v1,v2,…,vn,u1,u2,…,un} ，C3={a1,a2,…,ak,b1,b2,…,bk,…,c1,c2,…,ck,e1,e2,…,ek,f1,f2,…,fk,…,g1,g2,…,gk}，由定理2.2知 ，π=(C1,C2,C3)是圖1,n+1的一個(gè)3-部極小公平劃分。證畢

3 主要結(jié)果及證明

定理3.1T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹當(dāng)且僅當(dāng)T=或Skn+1,n+1.

為了證明定理3.1下面給出幾個(gè)引理：

引理3.2T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，則T的葉子一定全部含在同一個(gè)單元中。

證明：假設(shè)有兩個(gè)以上的單元含有葉子，不妨設(shè)C1與C2中都有葉子，那么由公平劃分得知：同一個(gè)單元中的點(diǎn)的度是相等的，所以C1與C2中只能有葉子，此時(shí)如果C1與C2中的點(diǎn)相鄰（或C1與C2都是自身相鄰），那么C1、C2都與C3不相鄰，這樣樹T就不連通，矛盾。所以，T的葉子只能全部含在同一個(gè)單元中。證畢

引理3.3T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，對任意單元Ci(i=1,2,3)，如果Ci中沒有葉子且與葉子相鄰，則Ci中的點(diǎn)自身不相鄰。

證明：因?yàn)門是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，由引理3.2知T的葉子一定全部含在同一個(gè)單元中，不妨設(shè)葉子全部含在C3中。假設(shè)C3中的點(diǎn)與C2中的點(diǎn)相鄰，那么C3中的點(diǎn)與C1中的點(diǎn)就不相鄰，如果C2中的點(diǎn)自身相鄰,而C2中的點(diǎn)又與C1中的點(diǎn)相鄰,于是對?v∈C2,就有d(v)≥3。這樣從樹T上刪去所有的葉子C3得到的樹沒有葉子,矛盾。因此C2中的點(diǎn)自身不相鄰,證畢

引理3.4T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，對任意單元Ci(i=1,2,3)，如果Ci中的點(diǎn)自身相鄰，則Ci中至多有兩個(gè)點(diǎn)。

證明：T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，不妨假設(shè)C1中的點(diǎn)自身相鄰，由引理3.2知，C1中沒有葉子，而且葉子全部含在同一個(gè)單元中，不妨設(shè)葉子全部含在C3中，由引理3.3知，C3只能與C2相鄰。由樹的連通性可知C2既與C3相鄰又與C1相鄰，現(xiàn)在刪去樹T上所有的葉子（C3中的點(diǎn)）得到的是樹T-C3，由于π=(C1,C2,C3)是樹T的極小公平劃分，所以樹T-C3具有2-部公平劃分φ=（C1,C2），根據(jù)引理3.3，在樹T-C3中，C2中的點(diǎn)全部是葉子。再從T-C3中刪去所有的葉子（C2中的點(diǎn)）得到的是樹T-C3-C2,這棵樹只剩下C1中的點(diǎn)，由于π=(C1,C2,C3)是樹T的極小公平劃分，所以樹T-C3-C2是正則的，要么是一個(gè)點(diǎn)，要么是一條邊，所以C1中至多有兩個(gè)點(diǎn)。證畢

定理3.1 的證明：充分性在定理2.3中已得證，下面證明必要性。設(shè)T是一棵具有3-部極小公平劃分π=(C1,C2,C3)的樹，由引理3.2不妨設(shè)葉子全部含在C3中且C3中的葉子與C2中的點(diǎn)相鄰，那么由引理3.3知C2中的點(diǎn)自身不相鄰，由樹的連通性知C2中的點(diǎn)必與C1中的點(diǎn)相鄰，根據(jù)引理3.4，C1中至多有兩個(gè)點(diǎn)，有兩種情況：當(dāng)C1中只有一個(gè)點(diǎn)時(shí)，C2中的所有點(diǎn)必與C1中的一個(gè)點(diǎn)相鄰，此時(shí)T-C3就是一個(gè)星圖，所以T=；當(dāng)C1中有兩個(gè)點(diǎn)時(shí)，由公平劃分知C1中的每個(gè)點(diǎn)與C2中相同個(gè)數(shù)的點(diǎn)相鄰，此時(shí)T-C3就是一個(gè)雙星圖，所以T=1,n+1。證畢

文獻(xiàn)[5]證明了所有的樹T=（n≠k2+k+1）、Skn+1,n+1恰有三個(gè)主特征值，結(jié)合定理3.1樹的3-部公平劃分與其主特征值的關(guān)系就非常清楚了。

［1］Cvetkovic D.M.The main part of the spectrum,divisors and switching of graphs,Publ.Inst.Math.（Beograd）1978,23（37）：31-38.

［2］侯耀平，周后卿.恰有兩個(gè)主特征值的樹［J］.湖南師范大學(xué)自然科學(xué)學(xué)報(bào)，2005,28（2）：1-3.

［3］HOU Yao Ping,TIAN Feng.Unicyclic graphs with exactly two main eigenvalues,Appl.Math.Lett.19（2006）：1143-1147.

［4］孫德榮，黃瓊湘.恰有兩個(gè)主特征值的圖與圖的剖分［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào),2012,35（2）：252-262.

［5］孫德榮，徐蘭.恰有三個(gè)主特征值的樹［J］.山東大學(xué)學(xué)報(bào)理科版,2013,48（2）：252-262.

［6］Hagos E.M.Some results on graph spectra,Linear Appl.2002,356：103-111.