几种复合图的Bartholdi Zeta函数

陈 语，陈海燕

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

1 预备知识

本文中考虑的图都是简单的连通图.令G是一个简单图,V(G)和E(G)分别表示图G的顶点集和边集.用degG(v) 表示图G中v的度,即与v关联的边的个数.设C=(e1,e2,…,en)是G的一个闭途径,令cbc(C)=|{i=1,2,…,n|ei+1=ei}|(这里en+1=e1)表示C中边回溯的次数.两个闭途径C1=(e1,e2…,en) 和C2=(f1,f2,…,fn)称为是等价的,若存在k使得fj=ej+k(modn),j=1,2,…,k,闭途径C所在的等价类记为[C].闭途径C的r次幂表示绕C的次数r所得的闭途径,记为Cr,若cbc(C)=cbc(C2)=0,则称C是约化的.进一步,若C不是一个比它严格小的闭途径的幂,则称C为素的.图G的Bartholdi Zeta函数定义如下[1]:

其中[C]为跑遍G中素闭途径的等价类.

当u=0时,Bartholdi Zeta 函数就退化成(Ihara) Zeta 函数[2]:

其中[C]跑遍G中素闭途径的等价类.

Ihara[2]首先证明了正则图的Zeta函数ZG(t)的倒数为多项式,随后相应的结果又被推广到一般图上[3].Bartholdi[1]提出了两个变量的Bartholdi Zeta 函数,并给出了它的一系列性质和它的行列式表达式.此后,针对进一步推广Bartholdi Zeta 函数以及研究它和图的各种性质之间的关系，引起了人们的广泛兴趣[4-7].本文中主要讨论3种复合图的Bartholdi Zeta 函数,首先给出它们的定义:给定一个图G,把G的每条边e=ab插入一个顶点ce所得到的图称为图G的 剖分图,记为S(G).对应图G的每条边e=(a,b)增加一个顶点ce,并把ce与顶点a和b相连所得的图称为G的 三角图,记为R(G).令I(G)={ce|e∈E(G)},则显然V(S(G))=V(R(G))=V(G)∪I(G).

定义1已知图G1和G2,G1和G2的三角点联图记为G1∨G2,定义为

V(G1∨G2)=V(R(G1))∪V(G2),

E(G1∨G2)=E(R(G1))∪E(G2)∪

{uv|u∈V(G1),v∈V(G2)}.

{uv|u∈V(G1),v∈V(G2)}.

定义3[8]已知图G1和G2,G1和G2的剖分边联图记为G1∨G2,定义为

V(G1∨G2)=V(S(G1))∪V(G2),

E(G1G2)=E(S(G1))∪E(G2)∪{uv|u∈

I(G1),v∈V(G2)}.

2.1 若干预备引理

设G是一个有n个顶点和m条边的图,令A(G),D(G),B(G)和L(G)分别表示它的邻接矩阵、度对角矩阵、关联矩阵和线图，则众所周知[9]:

B(G)TB(G)=A(L(G))+2Im,

这里B(G)T是B(G)的转置,Im是m阶单位矩阵.进一步地如果G是r-正则图,那么

B(G)B(G)T=A(G)+rIn.

FG(λ,μ)=det(λIn-(A(G)-μD(G))),

则图G的Bartholdi Zeta函数与广义特征多项式之间的关系是本文中计算的出发点.

引理1[11-12]设G是n个顶点和m条边的连通图,则

FG(λ,μ)=

此外还需要下面关于矩阵的两个结论:

引理2[12]令M1,M2,M3和M4分别是p×p,p×q,q×p和q×q阶矩阵,其中M1,M4可逆，则

2.2 主要结论

本节中给出本研究主要结论及其证明.首先先引入一些符号.

设Jm×n表示m行n列的全一矩阵.M是一个n阶矩阵,ΓM(x) 表示(xIn-M)-1所有的元素和,即

给定u,v,令:

(i)β=1-(1-u)2t2,

(ii)γ1=1+(1-u2)t2,

(iii)γ2=1+(1-u)(1+u+n2)t2,

定理1设图G1是有n1个顶点和m1条边的r-正则图,G2是有n2个顶点和m2条边的任意图.记r=λ1≥λ2≥…≥λn1为A(G1) 的特征值,则

(2r+n2)(1-u)t2-αn1t-rt)γ1-2rt2]

n2)(1-u)t2-λit)γ1-rt2-λit2]

证明首先由图G1∨G2的定义知道,它有n1+m1+n2个顶点,3m1+m2+n1n2条边,所以由引理1,有

ZG1∨G2(u,t)-1=

(1)

对G1∨G2的顶点做适当标号使得其邻接矩阵和度对角矩阵有如下形式:

D(G1∨G2)=

由引理2可得

r-λi]，

从而得到下面的关系式:

r-λi].

(2)

再由引理1得

(3)

(1-u)t,整理可得结果.

定理2假设图G1是有n1个顶点和m1条边的r-正则图,G2是有n2个顶点和m2条边的任意图.记r=λ1≥λ2≥…≥λn1为A(G1) 的特征值,从而

(r+n2)(1-u)t2-αn1t)γ1-2rt2]·[β+

采用与定理1相同的方法计算可得下面的结论.

下面要讨论边剖分边联图G1和G2的Bartholdi Zeta函数.

定理3假设图G1是有n1个顶点和m1条边的r-正则图,G2是n2个顶点和m2条边的任意图.记r=λ1≥λ2≥…≥λn1为A(G1) 的特征值,从而

[(γ2-αm1t)(β+r(1-u)t2)-2rt2]

证明由图G1G2的定义知,它有n1+m1+n2个顶点,2m1+m1n2+m2条边,所以由引理1,有

ZG1∨G2(u,t)-1=

对顶点进行合适的标号,可以得到G1∨G2的邻接矩阵和度对角矩阵分别如下:

A(G1

D(G1G2)=

现在回顾两个结论

(i)Jm1×m1的特征值分别为m1,0,…,0;

(ii) 因为G1是r-正则,所以它的线图L(G1) 是2r-2-正则.进一步得到A(L(G1))的特征值为λi+r-2,i=1,…,n1,并且特征值-2的重数为m1-n1.

所以本文中可以得到:

后面的证明过程与定理1相似,易得定理3.

证毕.

[1] BARTHOLDI L.Counting paths in graphs[J].Ensignment Math,2000,45(1):83-131.

[2] IHARA Y.On discrete subgrouos of the two by two project linear group over p-adic fields[J].Matematika,1966,18(18):98-115.

[3] BASS H.The Ihara-Selberg zeta function of a tree lattice[J].Internat J Math,1992,3:717-797.

[4] FOATA D,ZEILBERGER D.A combinatorial proof of bass′s evaluations of the Ihara-Selberg zeta function for graphs[J].Trans Amer Math Soc,1999,351:2257-2274.

[5] STARK H M,TERRAS A A.Zeta functions of finite graphs and coverings[J].Adv Math,1996,121:124-165.

[6] STARK H M,TERRAS A A.Zeta functions of finite graphs and coverings,Part Ⅱ[J].Adv Math,2000,154:132-195.

[7] KOTANI M,SUNADA T.Zeta functions of finite graphs[J].J Math Sci U Tokyo,2000,7(1):7-25.

[8] INDULAL G.Spectrum of two new joins of graphs and infinite families of integral graphs[J].Kragujevac J Math,2012,36(1):133-139.

[9] CVETKOVI′C D M,ROWLINSON P,SIMMI′C H.An introduction to the theory of graph spectra[M].Cambridge:Cambridge University Press,2010:217-244.

[10] CVETKOVI′C D M,DOOB M,SACHS H.Spectra of graphs[M].New York:Academic Press,1982:22-28.

[11] KIM H K,LEE J.A generalized characteristic polynomial of a graph having a semifree action[J].Discrete Math,2008,308(4):555-564.

[12] ZHANG F Z.Theschur complement and its applications[M].Berlin:Springer,2005:1-15.