基金项目:国家自然科学基金(11171134,11301217); 福建省自然科学基金(2015J01017,2013J01014)
通信作者:chey5@jmu.edu.cn
(School of Sciences,Jimei University,Xiamen 361021,China)
DOI: 10.6043/j.issn.0438-0479.201802013
图G的Ihara zeta 函数是一个一元函数.首先用代数方法得到了两个正则图联图的Ihara zeta函数的一个因子乘积表达式,在此基础上得到了正则图联图的3种基尔霍夫指标(基尔霍夫指标、度和基尔霍夫指标和度乘基尔霍夫指标)之间的一个关系式.
The Ihara zeta function of graph G is a function with one variable.In this paper,by the algebraic method,we first obtain a factorial product expression of Ihara zeta function of join graph.Then based on the expression,we obtain a relationship among three Kirchhoff indices i.e.Kirchhoff index,additive degree-Kirchhoff index,and multiplicative degree-Kirchhoff index.
本文中考虑的图都是简单的连通图.令G是一个简单图,V(G)和E(G)分别表示图G的顶点集和边集.用deg G(v)表示图G中顶点v的度,即与v关联的边的个数.设C=(e1,e2,…,en)是G的一个闭途径,令cbc(C)=|{i=1,2,…,n|ei+1=e-1i}|(这里en+1=e1)表示C中边回溯的次数.两个闭途径C1=(e1,e2,…,en)和C2=(f1,f2,…,fn)称为是等价的,若存在k使得fj=ej+k(mod n),j=1,2,…,k,闭途径C所在的等价类记为[C].闭途径C的r次幂表示r次绕C所得的闭途径,记为Cr,若cbc(C)=cbc(C2)=0,则称C是约化的.进一步,若C不是一个比它严格小的闭途径的幂,则称C为素的.图G的Ihara zeta函数定义为[1]:
ZG(u)=∏[C](1-u|C|)-1,
其中[C]是跑遍G中素闭途径的等价类.
设G为有n个顶点和m条边的图,A(G)和D(G)分别表示图G的邻接矩阵和度对角矩阵.令
fG(u)=det(In-u A(G)+u2(D(G)-In)),
则Bass[2]证明了如下关系式:
ZG(u)-1=(1-u2)m - nfG(u).(1)
图G的Ihara zeta函数与图的很多不变量都有紧密的联系,如顶点数、边数、围长、邻接谱等.特别是当G是一个最小度大于1的连通图时,Northshield[3]和Somodi[4]分别得到了Ihara zeta函数和生成树数目τ(G),以及基于等效电阻距离rij[5]的各种指标之间的关系,具体如下:
fG'(1)=2(m-n)τ(G); (2)
fG″(1)=2(Kf*(G)-2Kf+(G)+4Kf(G)+2mn-2n2+n)τ(G); (3)
这里
Kf(G)=∑1≤i<j≤nrij,
Kf+(G)=∑1≤i<j≤n(di+dj)rij,
Kf*(G)=∑1≤i<j≤ndidjrij
分别表示图G的基尔霍夫指标[6-7]、度和基尔霍夫指标[8-10]、度乘基尔霍夫指标[11-12],di,dj表示顶点vi,vj的度.
本文中首先用代数方法得到两个正则图联图的Ihara zeta函数的一个因子分解式,然后结合所得结果和式(2)和(3)得到了一些特殊图的生成树数目及其以上3种基尔霍夫指标之间的关系式.
给定两个图G1和图G2,它们的联图G记为G1∨G2,是顶点集V(G)=V(G1)∪V(G2),边集E(G)=E(G1)∪E(G2)∪{uv:u∈V(G1),v∈V(G2)}的图,如K3∨K2(图1).
图1 图K3,K2,P2[K3∨K2]
Fig.1 Figure K3,K2,P2[K3∨K2]
In表示n阶单位矩阵,Jp×q表示p×q阶全1矩阵.
设G是有n个顶点的图,G(x)=det(xIn-A(G))表示G的特征多项式.
引理1[13] 令M1,M2,M3和M4分别是p×p,p×q,q×p,和q×q阶矩阵,其中M1,M4可逆,则
det[M1 M2
M3 M4]=
det(M4)·det(M1-M2M -14M3)=
det(M1)·det(M4-M3M -11M2).
引理2[14] 设M是一个n阶矩阵,ΓM(x)表示(xIn-M)-1所有的元素和,即ΓM(x)=J1×n(xIn-M)-1Jn×1.如果M的每行元素和等于t,则
ΓM(x)=n/(x-t).
以下给出本研究的主要结论.
定理1 设图G1是有n1个顶点和m1条边的r1-正则图,G2是有n2个顶点和m2条边的r2-正则图,则联图G=G1∨G2有n=n1+n2个顶点,m=m1+m2+n1n2条边,它的Ihara zeta函数为
ZG(u)-1=(1-u2)m-nun(1-
(n1n2u2)/((x1-r1u)(x2-r2u)))</sub>G1((x1)/u)</sub>G2((x2)/u),
其中x1=1+(r1+n2-1)u2,x2=1+(r2+n1-1)u2.
证明 由式(1),根据联图的定义知,对G的顶点做适当标号,它的邻接矩阵和度对角矩阵可写成如下形式:
A(G1∨G2)=[A(G1)Jn1×n2
Jn2×n1 A(G2)],
D(G1∨G2)=[(r1+n2)In1 0n1×n2
0n2×n1(r2+n1)In2].
因此
fG(u)=det[x1In1-u A(G1)-u Jn1×n2
-u Jn2×n1 x2In2-u A(G2)],
其中x1=1+(r1+n2-1)u2,x2=1+(r2+n1-1)u2,则由引理1和2得
fG(u)=det(x1In1-u A(G1))det(x2In2-u A(G2)-u Jn2×n1(x1I-u A(G1))-1u Jn1×n2)=
det(x1In1-u A(G1))det(x2In2-u A(G2)-
(n1u2)/(x1-ur1)Jn2×n2)=
(1-(n1n2u2)/((x1-u r1)(x2-u r2)))det(x1In1-
u A(G1))det(x2In2-u A(G2))=
(1-(n1n2u2)/((x1-u r1)(x2-u r2)))un1+n2
det((x1)/uIn1-A(G1))det((x2)/uIn2-A(G2))=
un1+n2(1-(n1n2u2)/((x1-u r1)(x2-u r2)))
G1((x1)/u)G2((x2)/u).
上面倒数第三个等式是由Jn2×n2和正则图G2的邻接矩阵A(G2)交换,且Jn2×n2的特征值为n2,0,…,0得到的.至此结论得证.
下面简记为
f1(u)=det((1+(r1+n2-1)u2)In1-
u A(G1))=un1G1((1+(r1+n2-1)u2)/u),
f2(u)=det((1+(r2+n1-1)u2)In2-
u A(G2))=un2G2((1+(r2+n1-1)u2)/u),
g(u)=1-n1n2u2·((1+(r1+n2-1)u2-ur1)(1+(r2+n1-1)u2-ur2))-1.
注意到在定理1的条件下有:n1r1=2m1,n2r2=2m2,所以进一步可得
f1(1)=G1(r1+n2),
f2(1)=G2(r2+n1),g(1)=0,
f1'(1)=n1G1(r1+n2)+
(r1+n2-2)'G1(r1+n2),
f2'(1)=n2G1(r2+n1)+
(r2+n1-2)'G2(r2+n1),
g'(1)=(n1r1+n2r2+2n1n2-2n1-2n2)/(n1n2)=
(2(m-n))/(n1n2),
g″(1)=(4m-2n)/(n1n2)-(8(m-n)2)/(n21n22)+
(2(r1r2-2r1-2r2+4))/(n1n2)-2.
由定理1的证明知
fG1∨G2(u)=g(u)f1(u)f2(u).(4)
由此结合式(2)和(3),可以得到下面两个推论:
推论1 设图G1是有n1个顶点和m1条边的r1-正则图,G2是有n2个顶点和m2条边的r2-正则图,则联图G=G1∨G2的生成树数目为
τ(G)=(G1(r1+n2)G2(r2+n1))/(n1n2).
证明 一方面由式(4)和g(1)=0可得
fG'(1)=g'(1)f1(1)f2(1)=
G1(r1+n2)G2(r2+n1)(2(m-n))/(n1n2);
另一方面由式(2)知
fG'(1)=2(m-n)τ(G).
结论得证.
推论2 设图G1是有n1个顶点和m1条边的r1-正则图,G2是n2个顶点和m2条边的r2-正则图,则对联图G=G1∨G2有
Kf*(G)-2Kf+(G)+4Kf(G)=2(m-n)((r1+n2-2)ln'G1(r1+n2)+(r2+n1-2)ln'G2(r2+n1)+1)+r1r2-n1n2-2(r1+r2)+4-(4(m-n)2)/(n1n2).
证明 一方面由式(4)知
fG″(1)=g″(u)f1(1)f2(1)+2(f1'(1)f2(1)+f1(1)f2'(1))g'(1)=G1(r1+n2)G2(r2+n1)(g″(1)+2(n1+n2))g'(1)+2((r2+n1-2)G1(r1+n2)'G2(r2+n1)+(r1+n2-2)
'G1(r1+n2)G2(r2+n1))g'(1)=τ(G)n1n2
(g″(1)+2ng'(1)+2((r1+n2-2)ln'G1(r1+n2)+(r2+n1-2)ln'G2(r2+n1))g'(1)).
另一方面由式(3)知
fG″(1)=2(Kf*(G)-2Kf+(G)+4Kf(G)+2mn-2n2+n)τ(G).
因此
2(Kf*(G)-2Kf+(G)+4Kf(G)+2mn-2n2+n)=n1n2(g″(1)+2ng'(1)+2(ln'G1(r1+n2)(r1+n2-2)+ln'G2(r2+n1)(r2+n1-2))g'(1)).
将g'(1)和g″(1)的值代入整理即可得所要的结论.
注1 推论1是早就已知的结果,但推论2却是新的.Kf(G),Kf+(G)和Kf*(G)都是基于等效电阻距离的3个指标,研究它们之间的关系是一个自然而有意义的问题.当G是一个r-正则图时,由定义很容易得到
Kf*(G)=r2Kf(G),Kf+(G)=2rKf(G).
当G是一棵n个顶点的树时,在文献[15]和[16]中已得到
Kf*(G)=4Kf(G)-(2n-1)(n-1),
Kf*(G)=4Kf(G)-n(n-1).
对于其他非正则图,迄今为止还没有相关的结果.这里给出了2个正则图联图3个指标间的一个关系式.
利用上一节的结论来得到一些特殊图类的Ihara zera函数,生成树的数目及其3个基尔霍夫指标之间的关系式.下面用G^-表示G的补图.
例1 完全二部图Kn1,n2.
很显然Kn1,n2=Kn1^-∨Kn2^-,因此由定理1、推论1和推论2得:
ZKn1,n2(u)-1=(1-u2)n1n2-n1-n2(1+
(n2-1)u2)n1(1+(n1-1)u2)n2·
(1-(n1n2u2)/((1+(n1-1)u2)(1+(n2-1)u2))),
τ(Kn1,n2)=nn2-11nn1-12,
Kf*(Kn1,n2)-2Kf+(Kn1,n2)+4Kf(Kn1,n2)=
2(n1n2-n1-n2)((n1(n2-1))/(n2)+(n2(n1-1))/(n1)+
1)-n1n2+4-(4(n1n2-n1-n2)2)/(n1n2).
例2 正则图的锥图.
给定一个图G,它的锥图记为cG,是G和K1的联图,即cG=G∨K1.设G是n个顶点、m条边的r正则图,则由定理1,推论1和推论2得:
Zc G(u)-1=(1-u2)m-1un(1+(n-1)u2)·
(1-(nu2)/((1-ru+ru2)(1+(n-1)u2)))·
G((1+ru2)/u),
τ(cG)=G(r+1),
Kf*(c G)-2Kf+(c G)+4Kf(c G)=2(m-1)·
(r-1)ln'G(r+1)+(4(m-1)(n-m))/n-n-2r+4.
例3 正则图的双锥图.
给定一个图G,它的双锥图记为sG,是G和K2^-的联图,即sG=G∨K2^-.设G是n个顶点,m条边的r正则图,则由定理1、推论1和推论2得:
Zs G(u)-1=(1-u2)m+n-2un(1+(n-1)u2)2
(1-(2n u2)/((1-ru+(r+1)u2)(1+(n-1)u2)))·
G((1+(r+1)u2)/u),
τ(s G)=(n1G(r+2))/2,
Kf*(s G)-2Kf+(s G)+4Kf(s G)=2(m+n-2)(rln'G(r+1)+(2(n-2))/(n1)+1)-2n-2r+4+(2(m+n-2)2)/n.