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

2022-07-15李晓琳陈海燕

厦门大学学报（自然科学版） 2022年4期

李晓琳，陈海燕

(集美大学理学院，福建厦门 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)可以很快得到它的生成树数目.