一類廣義雙錐圖的生成樹數(shù)目

李曉琳，陳海燕

(集美大學(xué)理學(xué)院，福建 廈門 361021)

圖的生成樹數(shù)目一直是圖論中較為熱門的研究課題之一，計算圖的生成樹數(shù)目的方法有許多，其中較為著名的兩個生成樹計算方法為:Laplacian矩陣樹定理和Feussner遞推公式.迄今為止，已得到不少的圖類的生成樹數(shù)目的具體表達(dá)式，如:扇圖[1-2]、輪圖[1-2]、梯圖[1-2]、基于圈或路的多重星[3]、雙心輪圖[4]、雙柄扇圖[4]等，其他關(guān)于圖的生成樹數(shù)目結(jié)果詳見文獻(xiàn)[5-9].

圖1 SP4(2,α,β),α=(1,2,1,3),β=(2,2,1,2)Fig.1 SP4(2,α,β),α=(1,2,1,3),β=(2,2,1,2)

由上面的定義，很容易看出，當(dāng)m=0,α=β=(1,…，1)=J時，SG(0,J,J)就是一般意義下的雙錐圖.本文主要考慮n個頂點(diǎn)路Pn的廣義雙錐圖的生成樹數(shù)目.陳東等[4]利用遞歸方法得到了SPn(0,J,J)(稱為雙柄扇圖)生成樹數(shù)目的具體表達(dá)式.本文將利用矩陣樹定理得到一般SPn(m,α,β)的生成樹數(shù)目的一個計算公式，在此基礎(chǔ)上對參數(shù)取一些特殊值時，給出相應(yīng)生成樹數(shù)目的顯式表達(dá)式，推廣了文獻(xiàn)[4]中的結(jié)果.

令G=(V,E)是n個頂點(diǎn)的圖，圖G的拉普拉斯矩陣為L(G)=D(G)-A(G),其中D(G)=diag(d1,d2,…,dn)是G的度對角矩陣，A(G)是G的鄰接矩陣.則有如下著名的矩陣-樹定理[10].

引理1設(shè)G=(V,E)是n個頂點(diǎn)的圖，L(G)是圖G的Laplacian矩陣，M為L(G)的任意n-1階子矩陣，則圖G的生成樹數(shù)目

τ(G)=|det(M)|.

特別地，對任意的s∈V(G),令L(G,s)表示由L(G)去掉s所對應(yīng)的行和列得到的n-1階子矩陣，則

τ(G)=det(L(G,s)).

1 廣義雙錐圖SPn(m，α,β)的生成樹數(shù)目

設(shè)廣義雙錐圖SPn(m,α,β)的頂點(diǎn)集為{s1,v1,…,vn,s2}，其中{v1,v2,…,vn}為路Pn的頂點(diǎn)集，α=(α1,α2,…,αn),β=(β1,β2,…,βn).為方便，記SPn=SPn(m,α,β),因此，SPn的Laplacian矩陣可以表示為：

所以

由引理1,馬上可以得到下面的定理.

定理1對廣義雙錐圖SPn(m,α,β),其中m≥0,α=(α1,α2,…,αn),β=(β1,β2,…,βn).令ti=αi+βi+2,2≤i≤n-1,則

τ(SPn(m,α,β))=det(A-BD-1C),

(1)

其中

證明由引理1，

τ(SPn(m,α,β))=det(L(SPn,s2))=

注意到，SPn(m,α,β)是平面圖，對于圖1所示的平面嵌入，其對偶圖可以看做廣義梯圖(見圖2).眾所周知，一個平面圖的生成樹數(shù)目等于其對偶圖的生成樹數(shù)目[10]，所以式(1)也可以用來求廣義梯圖的生成樹數(shù)目.式(1)是一個二階行列式，對任意給定的參數(shù)m,n,α,β,由式(1)可以很快得到它的生成樹數(shù)目.

圖2 圖1的對偶圖Fig.2 Duel graph of fig.1

例1對廣義雙錐圖SP4(2,α,β)，α=(1,2,1,3),β=(2,2,1,2),有

所以由式(1)計算得

τ(SG(2,α,β))=det(A-BD-1C)=2 723.

下一部分對一些特殊形式的參數(shù)α,β給出其生成樹數(shù)目的具體表達(dá)式.

2 一些特殊廣義雙錐圖SPn(m，α，β)的生成樹數(shù)目

首先給出幾個引理.

引理2設(shè)n≥1，t是一個未定元，則n階矩陣

可逆，且

An(t)-1=

這里p0(t)=1,p1(t)=t，pk(t)=tpk-1(t)-pk-2(t),k≥2.

證明直接驗(yàn)證An(t)An(t)-1=In.

自2012年國內(nèi)磷復(fù)肥表觀消費(fèi)量達(dá)到峰值以來，中國磷復(fù)肥行業(yè)開始進(jìn)入供給側(cè)結(jié)構(gòu)性改革的大周期，行業(yè)發(fā)展從量的充足向質(zhì)的提升轉(zhuǎn)型。面對問題與困難，國內(nèi)磷復(fù)肥企業(yè)積極去產(chǎn)能、調(diào)結(jié)構(gòu)、提高核心競爭力，不斷培育新的增長點(diǎn)。

求解pk(t)所滿足的線性遞歸關(guān)系：

pk(t)=tpk-1(t)-pk-2(t),p0(t)=1,p1(t)=t.

很容易得到

(2)

其中

由式(2)馬上可以得到下面的結(jié)果.

(3)

且

(4)

證明利用式(2)和等比數(shù)列求和公式可得.

由引理3和定理1,可以得到下面的結(jié)論.

(5)

其中

t=a+b+2,t1=a+c+1.

證明既然α=(a,a,…,a),β=(c,b,…,b,c),式(1)中的A,B,C,D分別有如下形式：

令t=a+b+2,t1=a+c+1,則由引理2得:

所以由式(3)和(4)

然后由

τ(SPn(m,α,β))=det(A-BD-1C),

直接得到結(jié)論.

(6)

L3=(t1-t)2pn-2(t)+2(t1-t)pn-1(t)+pn(t).

(7)

推論1設(shè)n≥4,α=(a,a,…,a),β=(b,b,…,b),pk(t)定義如上.則

τ(SPn(m,α,β))=(nab+ma+mb)pn-1(t),

(8)

其中t=a+b+2.

證明令c=b代入定理2,即這時t1-t=-1,所以由式(6)和(7)得

L3=pn-2(t)-2pn-1(t)+pn(t)=

(t-2)pn-1(t)=(a+b)pn-1(t).

然后由式(5)得

(apn-1(t))2=(nab+ma+mb)pn-1(t).

τ(Pn∨K2)=(n+2)pn-1(4)=

上面的結(jié)果與文獻(xiàn)[4]所得結(jié)果相一致.

推論2設(shè)n≥4,α=(a,a,…,a),β=(b+1,b,…,b,b+1),pk(t)定義如上.則

(9)

其中t=a+b+2.

證明令c=b+1代入定理2,這時t1-t=0,所以有

L3=pn(t).