上一节主要得到了有关广义边冠图的normalized Laplacian谱,作为这一结果的应用,本节计算广义边冠图的degree-Kirchhoff指标和生成树数目.
假设图G是一个有n个顶点与m条边的简单连通图,它的normalized Laplacian特征值为0=δ1≤δ2≤…≤δn.图G的degree-Kirchhoff指标Kf*(G)由Chen等[4]定义如下:
Kf*(G)=∑i<jdidjrij,
其中,di与dj表示图G的顶点i与j的度,rij表示图G的顶点i和j之间的电阻距离.同时他们证明了对于一个含有n个顶点与m条边的简单连通图,其degree-Kirchhoff指标为
Kf*(G)=2m∑nj=21/(δj),
其中,δj为图G的非零normalized Laplacian特征值.关于计算生成树数目的方法有多种,这里主要研究利用图的normalized Laplacian谱进行计算.设G是一个有n个顶点与m条边的简单连通图,则其生成树数目的公式如下[5]
t(G)=1/(2m)∏ni=1di∏nj=2δj,
其中,di表示图G中顶点i的度,δj为图G的非零normalized Laplacian特征值.
引理3 设K2是两个顶点的完全图,H是一个有n2个顶点的r2-正则图,0=δ1≤δ2≤…≤δn2 是图H的normalized Laplacian特征值,则边冠图K2H的degree-Kirchhoff 指标是
Kf*(K2H)=(1+n2)(2+r2)+
((1+n2)(2+4n2+n2r2))/(2+n2)+(2+4n2+
n2r2)(2+r2)∑n2i=21/(r2δi+2).
证明 由定理1可知,边冠图K2H的norma-lized Laplacian谱是
0,(2+n2)/(1+n2),(2+4n2+n2r2)/((1+n2)(2+r2)),(r2δ2+2)/(r2+2),
(r2δ3+2)/(r2+2),…,(r2δn2+2)/(r2+2),
又有|E(K2H)|=1+(n2r2)/2+2n2=(2+4n2+n2r2)/2,则K2H的degree-Kirchhoff 指标为
Kf*(K2H)=(2+4n2+n2r2)((1+n2)/(2+n2)+
((1+n2)(2+r2))/(2+4n2+n2r2)+(r2+2)/(r2δ2+2)+(r2+2)/(r2δ3+2)+
…+(r2+2)/(r2δn2+2))=(1+n2)(2+r2)+
((1+n2)(2+4n2+n2r2))/(2+n2)+(2+4n2+
n2r2)(2+r2)∑n2i=21/(r2δi+2).
由此引理得证.
定理2 设G是一个有n1个顶点与m条边的r1-正则图,H1,H2,…,Hm都是有n2个顶点的r2-正则图,则广义边冠图G[Hi]m1的degree-Kirchhoff指标是
Kf*(G[Hi]m1)=((n2r2+4n2+2)2)/(2(n2+2))Kf*(G)+
m∑mi=1Kf*(K2Hi)+
(m(r2+2)(2+n2r2+4n2)(m-n1))/2+
(m-m2)(1+n2)(r2+2)+
((r2n2+4n2+2)[m(r2+2)(n1-1)-m2(n2+1)])/(2+n2).
证明 由广义边冠图G[Hi]m1 的定义可知,其边数|E(G[Hi]m1)|=m/2(2+4n2+n2r2).由推论(1)可知,当δ1=0时,ξ1=((r2+4)n2+2)/((r2+2)(n2+1)),(-overξ)1=0; 当δj≠0时,1/(ξj)+1/((-overξ)j)=(n2(r2+4)+(r2+2)δj+2)/(δj(n2+2)),则广义边冠图G[Hi]m1 的degree-Kirchhoff 指标为
Kf*(G[Hi]m1)=m(2+4n2+
n2r2)(((r2+2)(m-n1))/2+∑n2i=2(r2+2)/(r2δ(1)i+2)+
∑n2i=2(r2+2)/(r2δ(2)i+2)+…+∑n2i=2(r2+2)/(r2δ(m)i+2)+
((r2+2)(n2+1))/((r2+4)n2+2)+
∑n1j=2(n2(r2+4)+δj(r2+2)+2)/(δj(n2+2)))=
m(2+4n2+n2r2)(((r2+2)(m-n1))/2+
(r2+2)∑ms=1∑ni=21/(r2δ(s)i+2)+((r2+2)(n2+1))/(r2n2+4n2+2)+
((r2+2)(n1-1))/(n2+2)+(n2(r2+4)+2)/(n2+2)∑n1j=21/(δj))=
((n2r2+4n2+2)2)/(2(n2+2))Kf*(G)+m(r2+2)(2+
n2r2+4n2)((m-n1)/2+∑ms=1∑n2i=21/(r2δ(s)i+2))+
m(r2+2)(n2+1)+
(m(r2n2+4n2+2)(r2+2)(n1-1))/(n2+2)=
((n2r2+4n2+2)2)/(2(n2+2))Kf*(G)+
(m(r2+2)(2+n2r2+4n2)(m-n1))/2+
m∑mi=1Kf*(K2Hi)-m2(1+n2)(r2+2)-
(m2(r2n2+4n2+2)(n2+1))/(n2+2)+
m(r2+2)(n2+1)+
(m(r2n2+4n2+2)(r2+2)(n1-1))/(n2+2)=
((n2r2+4n2+2)2)/(2(n2+2))Kf*(G)+
m∑mi=1Kf*(K2Hi)+
(m(r2+2)(2+n2r2+4n2)(m-n1))/2+
(m-m2)(1+n2)(r2+2)+
((r2n2+4n2+2)[m(r2+2)(n1-1)-m2(n2+1)])/(2+n2).
定理得证.
利用图的生成树的数目与其Laplacian特征值之间关系,下面的引理是显然的.
引理4 设K2是两个顶点的完全图,H是一个有n2个顶点的r2-正则图,0=μ1≤μ2≤…≤μn2是图H的Laplacian特征值,则边冠图K2H的生成树数目为
t(K2H)=(n2+2)(μ2+2)(μ3+2)…
(μn2+2).
定理3 设G是一个有n1个顶点与m条边的r1-正则图,H1,H2,…,Hm都是有n2个顶点的r2-正则图,则广义边冠图G[Hi]m1 的生成树数目是
t(G[Hi]m1)=
(2/(n2+2))m-n1+1t(G)∏mi=1t(K2Hi).
证明 类似定理2的证明过程,可知G[Hi]m1的所有非零normalized Laplacian特征值的乘积为
∏δ=(2/(r2+2))m-n1(∏n2i=2(2+r2δ(1)i)/(r2+2)
∏n2i=2(2+r2δ(2)i)/(r2+2)…∏nni=2(2+r2δ(m)i)/(r2+2).
((r2+4)n2+2)/((r2+2)(n2+1))∏n1j=2(δj(n2+2))/((r2+2)(n2+1))=
(2m-n1(n2+2)n1-1(r2n2+4n2+2))/((r2+2)mn2(n2+1)n1)
∏n1j=2δj∏ms=1∏n2i=2(2+r2δ(s)i).(1)
又因为图Hi(1≤i≤m)的 normalized Laplacian特征值是0=δ(i)1≤δ(i)2≤…≤δ(i)n2,且Hi是r2-正则图,于是Hi的Laplacian特征值是0=r2δ(i)1≤r2δ(i)2≤…≤r2δ(i)n2.
∏δ=(2m-n1(n2+2)n1-1(r2n2+4n2+2))/((r2+2)mn2(n2+1)n1)
∏n1j=2δj∏ms=1∏n2i=2(2+r2δ(s)i)=
(2m-n1(n2+2)n1-m-1(r2n2+4n2+2))/((r2+2)mn2(n2+1)n1)
∏n1j=2δj∏mi=1t(K2Hi)=
(2m-n1(n2+2)n1-m-1(r2n2+4n2+2)n1)/((r2+2)mn2(n2+1)n1rn1-11 )
t(G)∏mi=1t(K2Hi).
因此G[Hi]m1 的生成树数目为
t(G[Hi]m1)=((r1+r1n2)n1(r2+2)n2m)/(m(2+4n2+n2r2))
∏δ=(2/(n2+2))m-n1+1t(G)∏mi=1t(K2Hi).
证毕.
