一类广义双锥图的生成树数目

李晓琳，陈海燕

(集美大学理学院，福建 厦门 361021)

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

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

令G=(V,E)是n个顶点的图，图G的拉普拉斯矩阵为L(G)=D(G)-A(G),其中D(G)=diag(d1,d2,…,dn)是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)).

1 广义双锥图SPn(m，α,β)的生成树数目

设广义双锥图SPn(m,α,β)的顶点集为{s1,v1,…,vn,s2}，其中{v1,v2,…,vn}为路Pn的顶点集，α=(α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).众所周知，一个平面图的生成树数目等于其对偶图的生成树数目[10]，所以式(1)也可以用来求广义梯图的生成树数目.式(1)是一个二阶行列式，对任意给定的参数m,n,α,β,由式(1)可以很快得到它的生成树数目.

图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.

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

2 一些特殊广义双锥图SPn(m，α，β)的生成树数目

首先给出几个引理.

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

可逆，且

An(t)-1=

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

证明直接验证An(t)An(t)-1=In.

自2012年国内磷复肥表观消费量达到峰值以来，中国磷复肥行业开始进入供给侧结构性改革的大周期，行业发展从量的充足向质的提升转型。面对问题与困难，国内磷复肥企业积极去产能、调结构、提高核心竞争力，不断培育新的增长点。

求解pk(t)所满足的线性递归关系：

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

很容易得到

(2)

其中

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

(3)

且

(4)

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

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

(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),

直接得到结论.

(6)

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

(7)

推论1设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)=

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

推论2设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).