图的生成树数目一直是图论中较为热门的研究课题之一,计算图的生成树数目的方法有许多,其中较为著名的两个生成树计算方法为:Laplacian矩阵树定理和Feussner递推公式.迄今为止,已得到不少的图类的生成树数目的具体表达式,如:扇图^[1-2]、轮图^[1-2]、梯图^[1-2]、基于圈或路的多重星^[3]、双心轮图^[4]、双柄扇图^[4]等,其他关于图的生成树数目结果详见文献[5-9].

若T是图G=(V,E)的一个生成子图,同时T又是一棵树,则称T为图G的一棵生成树.每个连通图都包含生成树,若两棵生成树的边集不同,则这两棵生成树不同.设图G和H是两个顶点不相交的图,则G和H的联图,记为G∨H,是顶点集为V(G)∪V(H),边集为E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)}的图.特别地,K₁∨G和K₂^-∨G分别称为G的锥图和双锥图,这里K_n表示n个顶点的完全图,K_n^-表示K_n的补图.本文考虑一类广义双锥图的生成树的数目,下面首先给出广义双锥图的定义.

定义1 设m为一个非负整数,设K^m₂是两个顶点(记为s₁,s₂)之间连m条边的图,G是顶点集为{v₁,v₂,…,v_n}的一个图.给定两个非负整数向量α=(α₁,α₂,…,α_n),β=(β₁,β₂,…,β_n),在K^m₂和G的并图的基础上,分别在s₁和v_i之间连接α_i条边,s₂和v_i之间连接β_i(1≤i≤n)条边所得到的图,称为图G的一个广义双锥图,记为SG(m,α,β).(路P₄的一个广义双锥图,如图1所示).

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

由上面的定义,很容易看出,当m=0,α=β=(1,…,1)=J时,SG(0,J,J)就是一般意义下的双锥图.本文主要考虑n个顶点路P_n的广义双锥图的生成树数目.陈东等^[4]利用递归方法得到了SP_n(0,J,J)(称为双柄扇图)生成树数目的具体表达式.本文将利用矩阵树定理得到一般SP_n(m,α,β)的生成树数目的一个计算公式,在此基础上对参数取一些特殊值时,给出相应生成树数目的显式表达式,推广了文献[4]中的结果.

令G=(V,E)是n个顶点的图,图G的拉普拉斯矩阵为L(G)=D(G)-A(G),其中D(G)=diag(d₁,d₂,…,d_n)是G的度对角矩阵,A(G)是G的邻接矩阵.则有如下著名的矩阵-树定理^[10].

引理1 设G=(V,E)是n个顶点的图,L(G)是图G的Laplacian矩阵,M为L(G)的任意n-1阶子矩阵,则图G的生成树数目

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

特别地,对任意的s∈V(G),令L(G,s)表示由L(G)去掉s所对应的行和列得到的n-1阶子矩阵,则

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

设广义双锥图SP_n(m,α,β)的顶点集为{s₁,v₁,…,v_n,s₂},其中{v₁,v₂,…,v_n}为路P_n的顶点集,α=(α₁,α₂,…,α_n),β=(β₁,β₂,…,β_n).为方便,记SP_n=SP_n(m,α,β),因此,SP_n的Laplacian矩阵可以表示为:

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

定理1 对广义双锥图SP_n(m,α,β),其中m≥0,α=(α₁,α₂,…,α_n),β=(β₁,β₂,…,β_n).令t_i=α_i+β_i+2,2≤i≤n-1,则

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

其中

证明 由引理1,

注意到,SP_n(m,α,β)是平面图,对于图1所示的平面嵌入,其对偶图可以看做广义梯图(见图1的对偶图
Fig.2 Duel graph of fig.1">图2).众所周知,一个平面图的生成树数目等于其对偶图的生成树数目^[10],所以式(1)也可以用来求广义梯图的生成树数目.式(1)是一个二阶行列式,对任意给定的参数m,n,α,β,由式(1)可以很快得到它的生成树数目.

例1 对广义双锥图SP₄(2,α,β),α=(1,2,1,3),β=(2,2,1,2),有

所以由式(1)计算得

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

下一部分对一些特殊形式的参数α,β给出其生成树数目的具体表达式.

图1的对偶图
Fig.2 Duel graph of fig.1">图1的对偶图
Fig.2 Duel graph of fig.1"/>

图2 图1的对偶图
Fig.2 Duel graph of fig.1

首先给出几个引理.

引理2 设n≥1,t是一个未定元,则n阶矩阵

可逆,且

这里p₀(t)=1,p₁(t)=t,p_k(t)=tp_k-1(t)-p_k-2(t),k≥2.

证明 直接验证A_n(t)A_n(t)^-1=I_n.

求解p_k(t)所满足的线性递归关系:

p_k(t)=tp_k-1(t)-p_k-2(t),p₀(t)=1,p₁(t)=t.

很容易得到

p_k(t)=1/(λ₁-λ₂)(λ^k+1₁-λ^k+1₂),(2)

其中

λ₁=(t+(t²-4)^1/2)/2,λ₂=(t-(t²-4)^1/2)/2.

由式(2)马上可以得到下面的结果.

引理3 令P^～_k(t)=∑^k_i=0p_i(t),k≥0,则有:

P^～_k(t)=(p_k+1(t)-p_k(t)-1)/(t-2),(3)

且

∑ⁿ_k=0P^～_k(t)=(p_n+1(t)-(n+2))/(t-2).(4)

证明 利用式(2)和等比数列求和公式可得.

由引理3和定理1,可以得到下面的结论.

定理2 设n≥4,α=(a,a,…,a),β=(c,b,…,b,c),p_k(t),P^～_k(t)(k≥0)定义同引理3.则

τ(SP_n(m,α,β))=L₁L₃-L²₂,(5)

其中

L₁=(a²)/(a+b)p_n-1(t)+(nab)/(a+b)+m,

L₂=a(t₁P^～_n-2(t)-P^～_n-3(t)+1),

L₃=t²₁p_n-2(t)-2t₁p_n-3(t)+p_n-4(t),

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

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

然后由

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

直接得到结论.

注:注意到p_k(t)=tp_k-1(t)-p_k-2(t),且tP_～k(t)-P^～_k-1(t)+1=P^～_k+1(t),所以式(5)中的L₂和L₃又可以表示为:

L₂=a((t₁-t)P^～_n-2(t)+P^～_n-1(t)),(6)

L₃=(t₁-t)²p_n-2(t)+2(t₁-t)p_n-1(t)+p_n(t).(7)

推论1 设n≥4,α=(a,a,…,a),β=(b,b,…,b),p_k(t)定义如上.则

τ(SP_n(m,α,β))=(nab+ma+mb)p_n-1(t),(8)

其中t=a+b+2.

证明 令c=b代入定理2,即这时t₁-t=-1,所以由式(6)和(7)得

L₂=a(P^～_n-1(t)-P^～_n-2(t))=ap_n-1(t),

L₃=p_n-2(t)-2p_n-1(t)+p_n(t)=

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

然后由式(5)得

τ(SP_n(m,α,β))=L₁L₃-L²₂=

((a²)/(a+b)p_n-1(t)+(nab)/(a+b)+m)((a+b)p_n-1(t))-

(ap_n-1(t))²=(nab+ma+mb)p_n-1(t).

例2 图P_n∨K^-₂和P_n∨K₂的生成数目.

很显然P_n∨K^-₂=SP_n(0,J,J),P_n∨K₂=SP_n(1,J,J),所以由式(8)和(2)得

τ(P_n∨K₂^-)=np_n-1(4)=(3^1/2n)/6((2+3^1/2)ⁿ-

(2-3^1/2)ⁿ),

τ(P_n∨K₂)=(n+2)p_n-1(4)=

(3^1/2(n+2))/6[(2+3^1/2)ⁿ-(2-3^1/2)ⁿ].

上面的结果与文献[4]所得结果相一致.

推论2 设n≥4,α=(a,a,…,a),β=(b+1,b,…,b,b+1),p_k(t)定义如上.则

τ(SP_n(m,α,β))=(2a²)/((a+b)²)(p_n(t)-

p_n-1(t)-1)+((nab)/(a+b)+m)p_n(t),(9)

其中t=a+b+2.

证明 令c=b+1代入定理2,这时t₁-t=0,所以有

L₂=aP^～_n-1(t)=a(p_n(t)-p_n-1(t)-1)/(a+b),

L₃=p_n(t).

然后由式(5)和p²_k-1(t)-p_k-2(t)p_k(t)=1,得

τ(SP_n(m,α,β))=L₁L₃-L²₂=

((a²)/(a+b)p_n-1(t)+(nab)/(a+b)+m)p_n(t)-

(a/(a+b)(p_n(t)-p_n-1(t)-1))²=

(a²)/((a+b)²)[tp_n-1(t)p_n(t)-p²_n(t)-p²_n-1(t)+

2(p_n(t)-p_n-1(t))-1]+((nab)/(a+b)+m)p_n(t)=

(2a²)/((a+b)²)(p_n(t)-p_n-1(t)-1)+

((nab)/(a+b)+m)p_n(t).