Zeta Functions of the Complement and xyz-Transformations of a Regular Graph

WANG Xueqin ()， DENG Aiping ()

College of Science， Donghua University， Shanghai 201620， China

Abstract: Let Z(λ， G) denote the zeta function of a graph G. In this paper the complement GC and the Gxyz-transformation Gxyz of an r-regular graph G with n vertices and m edges for x， y， z∈{0， 1， +， -}， are considerd. The relationship between Z(λ， G) and Z(λ， GC) is obtained. For all x， y， z ∈{0， 1， +， -}， the explicit formulas for the reciprocal of Z(λ， Gxyz) in terms of r， m， n and the characteristic polynomial of G are obtained. Due to limited space， only the expressions for Gxyz with z=0， and xyz∈{0++， +++， 1+-} are presented here.

Key words: regular graph; complement;xyz-transformation; zeta function

Introduction

The zeta function of a graph originates from the Riemann zeta function， and is introduced into graph theory by Ihara in his work onp-adic groups in the 1960 s[1]. Since that， zeta functions of graphs have been widely investigated. Several extensions of Ihara zeta function for graphs were raised and studied， such as weighted zeta function， Bartholdi zeta function， andL-function， see Refs. [2-10] and their references.

Graph coverings and graphs obtained under some operations， as useful techniques connecting algebra and graph theory， have been researched in many articles[3， 8-14]. In Ref. [3], Bass studied the zeta function of a uniform lattice on a tree and generalized Ihara’s result on zeta functions of regular graphs to general graphs. In a series of papers， Terrasetal. discussed the coverings of graphs to obtain possible versions of Riemannh ypothesis for the Ihara zeta function of graphs[8-10]. Kwak and Sato presented the zeta functions for the line， middle and total graphs of a graph and its covering[13]. Cooper and Prassidis discussed the zeta functions for infinite graph bundles[14]. Recently， Chen and Chen presented the explicit expressions of the Bartholdi zeta function for three kinds of graphs obtained by some join operations[15].

This work focuses on the (Ihara) zeta functions of graphs， obtained from a graph under some unary operations. In Ref. [16]， Dengetal. defined a unary operation on a graphG， to obtain a class of graphs， calledxyz-transformationsG， where xyz∈{0++， +++， 1+-}. Thesexyz-transformations includeC00+，G+0+，G0++，G0+0andG+++which have occurred in literatures[13， 17]. Among themG00+，G0++andG+++were also called subdivision， middle and total graphs ofG， respectively.

Since for {x，x′}， {y，y′}， {z，z′}={0， 1} or {+， -} the transformationsGxyzandGx′y′z′are the complements to each other， it is natural to consider the relationship between a graph and its complement in terms of the zeta function ofG. Theoretically we can obtain the zeta function of from that ofGx′y′z′from thatGxyzwhen they are the complements to each other. In Ref. [13]， the zeta functions ofG0++andG+++were given in terms of the characteristic polynomial ofGand the spectrum ofG， respectively. We obtain the zeta functions ofGxyzfor allx，y，z∈{0, 1, +, -} in terms of the characteristic polynomial ofG. Our results is a generalization of the corresponding results in Ref. [13]. Due to the limitation of the article， we present here only the zeta function forGxyzwithz=0 andxyz∈{0++， +++， 1+-}.

This paper proceeds as follows. In section 1， we introduce main notation， notions and some preliminaries. In section 2， we give the relationship between the zeta function of a regular graphGand its complement， and an example that supports the result. In section 3， we present the explicit formulas of the zeta functions forGxyzwithz={0} andxyz∈{0++， +++， 1+-}. We conclude our main results in section 4.

1 Preliminaries

LetGbe a simple connectedr-regular graph with vertex setV(G)={v1，v2，…，vn} and edge setE(G)={e1，e2， …，em}. The incidence matrixQ=Q(G) ofGis then×mmatrix (qij)， whereqij=1 if vertexviis incident to edgeejand otherwise，qij=0. The adjacency matrixA=A(G) ofGis then×nmatrix (aij)， whereaijif vertexviis adjacent to vertexvjandaij=0， otherwise. LetInbe the identityn×nmatrix andJmnthe all-onesm×nmatrix. We omit the subscript when it is clear from the context. The characteristic polynomial ofGisA(λ，G)=det(λI-A). LetD=D(G) be the diagonal matrix ofGwith thei-th diagonal entry the degree ofvi. We callDthe degree matrix ofG.

The zeta function of a graphGis defined by

(1)

whereλ∈with |λ| sufficiently small， [C] runs over all equivalence classes of primitive cycles ofG， and |C| is the length ofC.

In Ref. [3]， it was shown that， for a connected graphGwithnvertices andmedges， the reciprocal of the zeta function ofGis

Z(λ，G)-1=(1-λ2)m-ndet(I-λA+λ2(D-I)),

(2)

The proof of Eq. (2) can also be referred to Refs. [8， 18-19]. Moreover， ifGisr-regular， we have

(3)

Next we introduce the terminologies related toxyz-transformations.

Given a graphG， its complementGCis the graph with vertex setV(GC)=V(G) and (u，v)∈E(GC) if and only if (u，v)?E(G) for anyu，v∈V(G) andu≠v.

A graphG=(V，E) is called (X，Y)-bipartite ifV=X∪Y，X∩Y=?， andE?X×Y. IfE=X×Y， thenGis called a complete (X，Y)-bipartite graph and is denoted byKXY. Given an (X，Y)-bipartite graphG， letGcb=KXYE(G). GraphGcbis called the (X，Y)-bipartite complement ofG.

The line graphGlof a graphGis the graph with vertex setE(G) and two vertices are adjacent inGif and only if the corresponding edges inGlare adjacent. Notice that ifGhas no parallel edges， and so ifGhas no loops， thenGlis simple.

Given a graphG=(V，E)， forx∈{0， 1， +， -}， letG0be the empty graph withV(G0)，G1the complete graph withV(G1)=V，G+=GandG-=GC.

LetB(G)(Bcb(G)) be the graph with vertex setV∪Esuch that (v，e) is an edge inB(G) (resp.， inBcb(G)) if and only ifv∈V，e∈E， and vertexvis incident (resp.， not incident) to edgeeinG. ThusB(C) is a (V，E)-bipartite graph andBcb(G)is the (V，E)-bipartite complement ofB(G).

Definition1[16]Given a graphGandx，y，z∈{0， 1，+，-}， thexyz-transformationGxyzofGis the graph with the vertex setV(Gxyz)=V∪Eand the edge setE(Gxyz)=E(Gx)∪E((Gl)y)∪E(W)， whereW=B(G) ifz=+，W=Bcb(G) ifz=-，Wis the graph withV(W)=V∪Eand with no edges ifz=0， andWis the complete bipartite graph with partsV(G) andE(G) ifz=1.

The following lemmas are some simple and useful observations.

Lemma1Given a graphGwithmedges， letGlbe the line graph ofGandQthe incidence matrix ofG. Then

(1)QQT=D(G)+A(G)， and

(2)QTQ=2Im+A(Gl).

Lemma2LetGbe anr-regular graph withnvertices andmedges. LetAandQbe the adjacency and the incidence matrix ofG， respectively. Letkbe a positive integer. Then

(1)QTJnk=2Jmk；

(2)QJmk=rJnk；

(3)JkmQT=rJkn；

(4)JknQ=2Jkm；

(5)JknA=rJkm；

(6)AJnk=rJnk.

The next two lemmas give the spectrum properties of the line graph and the complement of a graph.

Lemma3[17， 20]LetGbe anr-regular graph withnvertices andmedges. LetGlbe the line graph ofG. Then

A(λ，Gl)=(λ+2)m-nA(λ-r+2，G).

Lemma4[21]LetGbe anr-regular graph withnvertices andmedges. LetGCbe the complement ofG. Then

The following lemma is useful when we calculate the zeta functions.

Lemma5[22-23]LetGbe anr-regular graph withnvertices andmedges andA=A(G). Letf(x，y) be an polynomial with two variablesx，yand real coefficients. Then the matrixf(A，Jnn) has determinant

2 Zeta Function of the Complement of G

Given anr-regular graphGwithnvertices andmedges， we present in this section the relationship between the zeta functions ofGand its complementGC.

Lemma6LetGbe anr-regular graph withnvertices andmedges. Then

By Lemma 4， we obtain the the expression ofZ(λ，GC)-1as desired.

Theorem1LetGbe anr-regular graph withnvertices andmedges. Then

(4)

where

(r-1)γ2-βγ+1=0，

and

For graphG， from Eq. (3) it follows that

A(β，G)=Z(γ，G)-1(1-γ2)n-mγ-n.

Now we conclude that

as desired.

Here we present some examples for Theorem 1.

Example1For the complete graphKn， by Eq. (3) we have

(5)

Now letKn， the empty graph withnvertices. By Eq. (1) we findZ(λ，G)-1=1.

Substitutingm=0，r=0 into the right side， sayR， of the Eq. (4)， we have

coinciding with Eq. (5).

coinciding with the left side of Eq. (4).

3 Zeta Function of Gxyz

Now we consider the zeta function of transformationsGxyz. LetGbe a connectedr-regular graph withnvertices andmedges. The adjacency matrix， the degree matrix and the incidence matrix ofGare denoted byA，D， andQ. We obtain the zeta functions ofGxyzfor allx，y，z∈{0， 1，+，-} in terms of the characteristic polynomial ofG[24]. Due to the limitation of the article， here we only provide the zeta function forGxyzwithz=0， and the zeta function ofG0++，G+++andG1+-.

3.1 Zeta function of Gxyz with z=0

Forz=0, notice thatGxyzis the disjoint union ofGxand (Gl)y. By Eq. (1)， it is clear that the zeta functions of a disconnected graph is the product of the zeta function of its connected components.

Lemma7IfGis graph withnvertices andmedges. Then

Z(λ，Gxy0)-1=Z(λ，Gx)-1Z(λ，(Gl)y)-1，

wherex，y∈{0， 1，+，-}

Here we listZ(λ，Gx)-1andZ(λ，(Gl)y)-1for allx，y∈{0， 1，+，-} The proof is based on Eq. (1) and Lemmas 3 and 4.

Lemma8LetGbe a graph withnvertices andmedges. Then

(1)Z(λ，G0)-1=1，Z(λ(Gl)0)-1=1.

Moreover， ifGisr-regular， thenGlis 2(r-1)-regular.

The above result for line graph in Lemma 8(3) can also be referred to Ref. [13， Theorem 9]. By Lemmas 8 and 9， we have the expression of the zeta function ofGxy0for all

x，y∈{0， 1， +， -}.

Theorem2LetGbe anr-regular graph withnvertices andmedges. Then

(1)Z(λ，G000)-1=1,

3.2 Zeta function of G0++， G+++ and G1+-

We present here the zeta functions ofG0++，G+++，G1+-. The proofs forG0++andG+++can also be referred to Ref. [13， Theorem 19， Theorem 30].

Theorem3LetGbe a connectedr-regular graph withnvertices andmedges. Then

(6)

ProofThe adjacency matrix and degree matrix ofG0++are

and

respectively. Then by Eq. (2)， we have

Z(λ，G0++)-1=(1-λ2)ε-vdet(Im+n-λA(G0++)+λ2(D(G0++)-Im+n))=(1-λ2)ε-vdetM，

whereε=m+mr，v=m+n，

Thus

whereδis shown in Eq. (6). By Lemma 3， we obtain

□

Theorem4LetGbe a connectedr-regular graph withnvertices andmedges. Then

Z(λ，G+++)-1=(1-λ2)(m+n)(r-1)λm+nA(，G+++)，

A(，G+++)=(+2)

and

ProofFirst we calculate the characteristic polynomial ofG+++, and

A(，
(multiply the first row by -Qand add the result to the second row)

(+2)m-n2+(2-r)-r)In-(2+3-r)A+A2=
(+2)

Then considering thatD(G+++)=2rIm+nand by Eq. (2)， we have

Z(λ，G+++)-1= (1-λ2)ε-vdet(Im+n-λA(G+++)+λ2(D(G+++)-Im+n(G+++))=
(1-λ2)ε-vdet((1-λ2)Im+n-λA(G+++)+λ2D(G+++))=
(1-λ2)ε-vdet(((2r-1)λ2+1)Im+n-λA(G+++))=
(1-λ2)ε-vλm+nA(，G+++)，

whereε=r(m+n)，v=m+n，

Note that in Ref. [13]， the expression forZ(λ，G+++)-1is in terms of the spectra ofG. Here our expression is in terms of the characteristic polynomial ofG， which is simpler.

Theorem5LetGbe a connectedr-regular graph withnvertices andmedges. Then

x1=(n+m-r-2)λ2+λ+1，

(7)

x2=(n+2r-5)λ2+2λ+1

(8)

(9)

(10)

and

(11)

ProofThe adjacency matrix and degree matrix ofG1+-are

and

respectively. Then by Eq. (2)， we have

Z(λ，G1+-)-1= (1-λ2)ε-vdet(Im+n-λA(G1+-)+λ2(D(G1+--Im+n))=
(1-λ2)ε-vdet((1-λ2)Im+n-λA(G1+-)+λ2D(G1+-))=
(1-λ2)ε-vdetN，

(12)

andx1andx2are shown in Eqs. (7) and (8)， respectively.

and adding the result to the second row. Thus

(13)

wherex3is shown in Eq. (9).

By Lemma 1(2)， we have

wheref1(Al，Jm)=x4Im+x3Jm-x5Al，wherex4andx5are shown in Eqs. (10) and (11)， respectively. By Lemma 5， we have

Combining Eqs. (12) and (13)， we have

□

4 Conclusions

Given anr-regular graphGwithnvertices andmedges， this article presents the relationship between the zeta functions ofGCandG. The explicit formulas ofZ(λ，Gxyz)-1for allx，y，z∈{0， 1， +， -} in terms ofr，m，nand the characteristic polynomial ofGcan be obtained. The result is a generalization of the corresponding results in Ref. [13]. Due to the limitation of the paper we only present here the expressions ofZ(λ，Gxyz)-1for z=0 andxyz∈{0++， +++， 1+-}. The formulas for otherGxyzare included in Wang’s master dissertation[24].