A New Proof of Bartholdi’s Theorem

A New Proof of Bartholdi’s Theorem

HIROBUMI MIZUNO

Department of Electronics and Computer Science, Meisei University, 2-590, Nagabuti, Ome, Tokyo 198-8655, Japan

IWAO SATO^∗,† [email protected]

Oyama National College of Technology, Oyama, Tochigi 323-0806, Japan Received September 25, 2002; Revised March 16, 2005; Accepted March 23, 2005

Abstract. We give a new proof of Bartholdi’s theorem for the Bartholdi zeta function of a graph.

Keywords: zeta function, graph, cycle, bump

1. Introduction

Zeta functions appear in number theory, algebraic geometry, spectral geometry, dynamical systems and graph theory. Many generalizations of the Riemann zeta function [5] have been found to be useful: Dirichlet L-function [13], Dedekind zeta function [13], Artin L-function [13], Selberg zeta function [17], Ruelle zeta function [16], Ihara zeta function [11]. These zeta functions have the properties in common: the rationality, the functional equation, the analogue of the Riemann hypothesis, the analogue of the prime number theorem. They bring many fruitful results in Mathematics. For example, the non-real zeros of them are useful to analyze the distribution of “primitive” elements (prime numbers, prime ideals, primitive closed geodesics, prime cycles etc) in various fields see [4, 10, 13, 17, 20, 21, 23].

Zeta functions of graphs started from p-adic Selberg zeta functions of discrete groups by Ihara [11]. At the beginning, Serre [18] pointed out that the Ihara zeta function is the zeta function of a regular graph. In [11], Ihara showed that their reciprocals are explicit polynomials. A zeta function of a regular graph G associated to a unitary representation of the fundamental group of G was developed by Sunada [20, 21]. Hashimoto [8] treated multivariable zeta functions of bipartite graphs. Bass [3] generalized Ihara’s result on zeta functions of regular graphs to irregular graphs. Various proofs of Bass’ theorem were given by Stark and Terras [19], Kotani and Sunada [12] and Foata and Zeilberger [6].

Bartholdi [2] extended a result by Grigorchuk [7] relating cogrowth and spectral radius of random walks, and gave an explicit formula determining the number of bumps on paths in a graph. Furthermore, he presented the “circuit series” of the free products and the

∗Supported by Grant-in-Aid for Science Research (C)

†Author to whom all correspondence should be addressed.

direct products of graphs, and obtained a generalized form “Bartholdi zeta function” of the Ihara(-Selberg) zeta function.

It seems that it is worth considering the Batholdi zeta function version of various zeta functions in number theory, etc, and the results in tree enumeration. It is for that purpose that we present another proof of Bartholdi’s theorem. Furthermore, Bartholdi’s theorem is a general result containing Bass’ theorem, and so giving new proofs of it is important as some new proofs of Bass’ theorem were given.

All graphs in this paper are assumed to be simple. Let G be a connected graph with vertex set V (G) and edge set E(G), and let R(G)= {(u, v),(v,u)|uv ∈ E(G)}be the set of oriented edges (or arcs) (u, v),(v,u) directed oppositely for each edge uv of G. For e = (u, v) ∈ R(G), u = o(e) andv = t(e) are called the origin and the terminal of e, respectively. Furthermore, let e⁻¹=(v,u) be the inverse of e=(u, v).

A path P of length n in G is a sequence P =(e1, . . . ,en) of n arcs such that ei ∈ R(G), t(ei) = o(ei+1)(1 ≤ i ≤ n−1). If ei = (vi−1, vi), 1 ≤ i ≤ n, then we also denote P by (v0, v1, . . . , vn). Set|P| =n, o(P)=o(e₁) and t(P)=t(en). Also, P is called an (o(P),t(P))-path. A (v, w)-path is called av-cycle (orv-closed path) ifv=w. The inverse cycle of a cycle C =(e₁, . . . ,en) is the cycle C⁻¹=(e_n⁻¹, . . . ,e⁻¹₁ ).

We introduce an equivalence relation between cycles. Two cycles C₁=(e₁, . . . ,em) and C₂=( f₁, . . . ,fm) are called equivalent if there exists an integer k such that fj =ej+kfor all j , where the subscripts are read modulo n. The inverse cycle of C is not equivalent to C if|C| ≥3. Let [C] be the equivalence class which contains a cycle C.

We say that a path P =(e1, . . . ,en) has a backtracking or a bump at t(ei) if e⁻¹_i+1 =ei

for some i (1≤i ≤n−1). Let B^rbe the cycle obtained by going r times around a cycle B. Such a cycle is called a multiple of B. Multiples of a cycle without bumps may have a bump. Such a cycle is said to have a tail. If its length is n−1, then the cycle can be written as

e₁, . . . ,ek= f₁, f₂, . . . , fn−2k,e_k⁻¹, . . . ,e⁻₁¹ ,

where ( f₁,f₂, . . . , fn−2k) is a cycle. A cycle C is reduced if C has no bump. Furthermore, a cycle C is prime if it is not a multiple of a strictly shorter cycle. Note that each equivalence class of prime, reduced cycles of a graph G passing through a vertexvof G corresponds to a unique conjugacy class of the fundamental groupπ1(G, v) of G atv.

The (Ihara) zeta function of a graph G is a function of a complex variable t with|t|

sufficiently small, defined by Z(G,t)=ZG(t)=

[C]

1−t^|C|₋₁ ,

where [C] runs over all equivalence classes of prime, reduced cycles of G.

Let G be a connected graph with n verticesv1, . . . , vn. The adjacency matrix A=A(G)= (ai j) is the square matrix such that ai j=1 ifviandvjare adjacent, and ai j =0 otherwise.

The degree of a vertexvi of G is defined by degvi = degGvi = |{vj|vivj ∈ E(G)}|. If degGv=k (constant) for eachv∈V (G), then G is called k-regular.

Ihara [11] showed that the reciprocal of the zeta function of a regular graph is an ex- plicit polynomial. The zeta function of a regular graph has the above three properties: the rationality; the functional equations; the analogue of the Riemann hypothesis see [22]. The analogue of the Riemann hypothesis for the zeta function of a graph is given as follows: Let G be any connected (q+1)-regular graph (q >1) and s =σ +i t (σ,t ∈R) a complex number. If ZG(q^−s)=0 and Res∈(0,1), then Res= ¹₂. A connected (q+1)-regular graph G is called a Ramanujan graph if for all eigenvaluesλof the adjacency matrix A(G) of G such thatλ= ±(q+1), we have|λ| ≤2√

q. This definition was introduced by Lubotzky, Phillips and Sarnak [14]. For a connected (q+1)-regular graph G, ZG(q^−s) satisfies the Riemann hypothesis if and only if G is a Ramanujan graph.

Hashimoto [8] treated multivariable zeta functions of bipartite graphs. Bass [3] general- ized Ihara’s result on the zeta function of a regular graph to an irregular graph, and showed that its reciprocal is a polynomial.

Theorem 1 (Bass) Let G be a connected graph. Then the reciprocal of the zeta function of G is given by

Z(G,t)⁻¹=(1−t²)^r−1det(I−tA(G)+t²(D−I)),

where r is the Betti number of G, and D =(di j) is the diagonal matrix with dii =degvi

and di j=0,i = j,(V (G)= {v1, . . . , vn}).

Stark and Terras [19] gave an elementary proof of Theorem 1, and discussed three different zeta functions of any graph. Various proofs of Bass’ theorem were known. Kotani and Sunada [12] proved Bass’ theorem by using the property of the Perron operator. Foata and Zeilberger [6] presented a new proof of Bass’ theorem by using the algebra of Lyndon words.

The complexityκ(G)(=the number of spanning trees in G) of a connected graph G is closely related to the zeta function of G. Hashimoto expressed the complexity of a regular graph as a limit involving its zeta function in [8]. For an irregular graph G, Hashimoto [9]

and Northshield [15] gave the value of (1−t)^−rZG(t)⁻¹at t=1 in term of the complexity of G, where r is the Betti number of G. Kotani and Sunada [12] presented its elementary proof.

Furthermore, Northshield [15] showed that the complexity of G is given by the derivative of the zeta function of G.

Cycles, reduced cycles and prime cycles in a digraph are defined in the same manner as the case of a graph. Let D be a connected digraph. Then the zeta function of D is a function of a complex variable t with|t|sufficiently small, defined by

Z(D,t)=ZD(t)=

[C]

1−t^|C|₋₁ ,

where [C] runs over all equivalence classes of prime cycles of D. The zeta function of a digraph is much easier to handle than that of a graph. For example, it is well-known cf, [4]

and easy to check

Z(D,t)⁻¹=det(I−A(D)t),

where A=A(D) is the adjacency matrix of D. Kotani and Sunada [12] have shown that the zeta function of a finite graph is equal to that of its oriented line graph, which is a strongly connected digraphs, and gave a simple proof of Bass’ theorem.

Let G be a connected graph. Then the bump count bc(P) of a path P is the number of bumps in P. Furthermore, the cyclic bump count cbc(C) of a cycle C =(e1, . . . ,en) is

cbc(C)=i =1, . . . ,nei =e_i⁻¹₊₁,

where en+1=e1. Then the Bartholdi zeta function of G is a function of complex variables u,t with|u|,|t|sufficiently small, defined by

ζG(u,t)=ζ(G,u,t)=

[C]

1−u^cbc(C)t^|C|₋₁ ,

where [C] runs over all equivalence classes of prime cycles of G. If u =0, then the Bartholdi zeta function of G is the (Ihara) zeta function of G.

Let n and m be the number of vertices and unoriented edges of G, respectively. Then two 2 m×2 m matrices B=(Be,f)e,f∈R(G)and J=(Je,f)e,f∈R(G)are defined as follows:

Be,f =

1 if t(e)=o( f ),

0 otherwise , Je,f =

1 if f =e⁻¹, 0 otherwise.

Bartholdi [2] presented a determinant expression for the Bartholdi zeta function of a graph.

Theorem 2 (Bartholdi) Let G be a connected graph with n vertices and m unoriented edges. Then the reciprocal of the Bartholdi zeta function of G is given by

ζ(G,u,t)⁻¹=det(I2m−(B−(1−u)J)t)

=(1−(1−u)²t²)^m−ndet(I−tA(G)+(1−u)(D−(1−u)I)t²).

The proof of Theorem 2 in [2] was long and used two results of Amitsur [1] relating determinants of many matrices and power series over a matrix ring.

In the case of u =0, Theorem 2 implies Theorem 1. If u =1, then Theorem 2 gives a determinant expression of the zeta function of the digraph obtained from a graph G by replacing each edge of G by two oppositely oriented edges.

In this paper, we present another proof of Theorem 2. The proof of the second formula in Theorem 2 is a combinatorial proof which only concentrates on the number of cycles in a graph. Although Bartholdi [2] considered all paths from x to y for all pairs of vertices x,y of a graph G in his proof of Theorem 2, we consider all paths of length m for all integer m, and present extensions of Lemmas 1 and 2 in Stark and Terras [19] to general paths. The proof of the first formula in Theorem 2 is a simple proof which is purely linear algebraic.

This is a shorter proof of Theorem 2. This result might have profound implications for number theory and tree enumeration, etc.

2. A proof of the second formula in Theorem 2

We give a proof of the second formula in Theorem 2. The proof is an analogue of the method of Stark and Terras [19].

Let G be a connected graph with n vertices and m unoriented edges. Futhermore, let V (G)= {v1, . . . , vn}and R(G)= {e1, . . . ,em,em+1, . . . ,e2m}such that em+i =e_i⁻¹(1≤ i ≤m).

Since

logζ(G,u,t)= −

[C]

log

1−u^cbc(C)t^|C|

=

[C]

∞ s=1

1

su^cbc(C)st^|C|s, we have

∂

∂t logζ(G,u,t)=t⁻¹

[C]

∞ s=1

|C|u^cbc(C)st^|C|s

=t⁻¹ ∞ s=1

C

u^cbc(C)st^|C|s

=t⁻¹

C₁

u^cbc(C1)t^|C1|,

where _C and _C1 denote the sum over all prime cycles C and all cycles C1 of G, respectively. Note that there exist|C|elements in [C], and cbc(C^s)=cbc(C)s. The third equality is obtained by the fact that each cycle of G is a multiple of some prime cycle of G.

LetCsbe the set of all cycles in G with length s. Set Ns =

C∈Cs

u^cbc(C).

Then,

∂

∂t logζ(G,u,t)=t⁻¹

s≥1

Nst^s. (1)

For s≥1, the n×n matrix As=((As)i,j)_1≤i,j≤nis defined as follows:

(As)i,j =

P

u^bc(P),

where (As)i,jis the (i,j )-component of As, and P runs over all paths of length s fromvi

tovjin G. Note that A1=A(G). Furthermore, let A0=In.

Lemma 1 Put Q=D−I. Then

A2=(A1)²−(1−u)D=(A1)²−(1−u)(Q+I) and

As =As−1A1−(1−u)As−2(Q+uI) f or s ≥3.

Proof: The first formula is clear. We prove the second formula. The proof is an analogue of the proof of Lemma 1 in [19].

We count the paths of length s fromvi tovkin G. Let s ≥3 and A(G)=(Ai,j). Then the sum _j(As−1)i,jAj,kcounts three types of paths P,Q,R in G as follows:

P =(e₁, . . . ,es−1,es),es=e⁻_s−1¹ , es=(vj, vk),

Q=(e1, . . . ,es−2,es−1,es), es−1 =e⁻¹_s−2, es=e⁻¹_s−1=(vj, vk), R=(e₁, . . . ,es−2,es−1,es), es−2 =e⁻_s−1¹ =es =(vj, vk).

Let T = (e1, . . . ,es−2). Then the term corresponding to P,Q and R in the sum

j(As−1)i,jAj,kis u^{bc(T )}, u^{bc(T )}and u^{bc(T )+1}, respectively. While, the term corresponding to P,Q and R in (As)i,kis u^{bc(T )}, u^{bc(T )+1}and u^{bc(T )+2}, respectively. Thus,

(As)i,k=

j

(As−1)i,jAj,k+(u−1)(As−2)i,kqk+(u²−u)(As−2)i,k,

where qk=degvk−1. Therefore, the result follows.

In ( _s≥0Ast^s)(I−tA₁+(1−u)(Q+uI)t²), the coefficient of t^sfor any s≥3 is 0 by the second formula of Lemma 1. Furthermore, by the first formula of Lemma 1, we have

s≥0

Ast^s

(I−tA1+(1−u)(Q+uI)t²)=(1−(1−u)²t²)I. (2)

Since (1−(1−u)²t²)⁻¹= j≥0(1−u)^{2 j}t^{2 j},

I=

k≥0

Akt^k

j≥0

(1−u)^{2 j}t^{2 j}

(I−tA₁+(1−u)(Q+uI)t²)

=

s≥0 [s/2]

j=0

As−2 j(1−u)^{2 j}t^s

(I−tA₁+(1−u)(Q+uI)t²). (3)

For s≥1, letCsbe the set of all cycles of length s with tails in G, and as=

C∈Cs

u^bc(C).

Then a₁=0 and a₂=2mu.

Lemma 2

as=Tr[(Q−(1−2u)I)As−2]+(1−u)²as−2 for s≥2.

Proof: We want to count cycles of length s with tails in G. The proof is an analogue of the proof of Lemma 2 in [19].

Let s ≥2. Then we have as =

n i=1

u^bc(C)C ⊃tail, |C| =s,C : vi-cycle

=

i,j ;(vi,vj)∈R(G)

u^bc(C)C ⊃tail, |C| =s,C =(vi, vj, . . .)

= n

j=1

(vi,vj)∈R(G)

u^bc(C)C ⊃tail, |C| =s,C =(vi, vj, . . .)

Letvjbe fixed. Furthermore, let C=(vi, vj, vl, . . . , vr, vj, vi) be any cycle of length s with tails in G, and let P =(vj, vl, . . . , vr, vj).

Case 1. P does not have a tail, i.e.,vl =vr. Then the cycle C is divided into two types:

C₁ =(vi, vj, vl, . . . , vr, vj, vi), vi=vl and vi =vr,

C2 =(vi, vj, vi, . . . , vr, vj, vi)(vl =vi) or (vi, vj, vl, . . . , vi, vj, vi)(vr =vi).

Case 2. P has a tail, i.e.,vl=vr.

Then the cycle C is divided into two types:

C3 =(vi, vj, vl, . . . , vl, vj, vi), vi =vl, C4=(vi, vj, vi, . . . , vi, vj, vi), vi =vl. Now, we have

u^bc(C1)=u^bc(C3)=u^bc(P), u^bc(C2)=u^bc(P)+1, u^bc(C4)=u^bc(P)+2.

Thus,

bj =

(vi,vj)∈R(G)

u^bc(C)C⊃tail, |C| =s,C=(vi, vj, . . .)

=(qj−1) u^bc(P)P ⊃tail,|P| =s−2, P : vj-cycle +2u u^bc(P)P ⊃tail, |P| =s−2,P : vj-cycle +qj u^bc(P)P ⊃tail, |P| =s−2,P : vj-cycle} +u² u^bc(P)P⊃tail, |P| =s−2,P : vj-cycle .

That is,

bj =(qj−1) u^bc(P)|P| =s−2,P : vj-cycle +2u u^bc(P)P ⊃tail, |P| =s−2,P : vj-cycle +(1+u²) u^bc(P)P⊃tail, |P| =s−2,P : vj-cycle

.

Therefore, it follows that as =

n j=1

bj

=

j

(qj−1) u^bc(P)|P| =s−2,P : vj-cycle +2u

j

u^bc(P)|P| =s−2,P : vj-cycle +(1−2u+u²)

j

u^bc(P)P ⊃tail,|P| =s−2, P : vj-cycle .

Hence,

as=Tr[(Q−I)As−2]+2uTr[As−2]+(1−u)²as−2.

Since cbc(C) = bc(C)+1 for each cycle C of length s with tails, we have Ns = Tr(As)−(1−u)as. Thus,

Ns =Tr

As−(1−u)⁻¹(Q−(1−2u)I)

[(s−1)/2]

j=1

(1−u)^{2 j}As−2 j

−

0 if s is odd,

(1−u)^s−1a₂ if s is even.

for s≥3, and

N1 =TrA1=0, N2=TrA2−(1−u)a2=2mu−(1−u)·2mu=2mu². Next, set

N^∗_s =As−(1−u)⁻¹(Q−(1−2u)I)

[s/2]

j=1

(1−u)^{2 j}As−2 j

=As+(1−u)⁻¹(Q−(1−2u)I)As

−(1−u)⁻¹(Q−(1−2u)I)

[s/2]

j=0

(1−u)^{2 j}As−2 j.

Then (2) and (3) imply that

s≥0

N^∗_st^s

(I−tA1+(1−u)(Q+uI)t²)

=(I+(1−u)⁻¹(Q−(1−2u)I))(1−(1−u)²t²)I−(1−u)⁻¹(Q−(1−2u)I)

=(1−(1−u)²t²)I−(1−u)t²(Q−(1−2u)I).

Since N^∗₀=A0=In,

s≥1

N^∗_st^s

(I−tA₁+(1−u)(Q+uI)t²)

=(1−(1−u)²t²)I−(1−u)t²(Q−(1−2u)I)−(I−tA1+(1−u)(Q+uI)t²)

=tA₁−2(1−u)(Q+uI)t². Therefore it follows that

s≥1

N^∗_st^s =(tA1−2(1−u)(Q+uI)t²)(I−tA1+(1−u)(Q+uI)t²)⁻¹.

By [19, Lemma 3], we have

Tr

s≥1

N^∗_st^s

=Tr

−t ∂

∂t log(I−tA1+(1−u)(Q+uI)t²)

.

For s≥1, we have Tr

N^∗_s

=Ns−

0 if s is odd,

(1−u)^sTr(Q−I) if s is even.

Thus,

Tr

s≥1

N^∗_st^s

=

s≥1

Nst^s−Tr(Q−I)

j≥1

(1−u)^{2 j}t^{2 j}

=

s≥1

Nst^s−Tr(Q−I) (1−u)²t² 1−(1−u)²t², i.e.,

s≥1

Nst^s =Tr

s≥1

N^∗_st^s

+Tr(Q−I)

j≥1

(1−u)^{2 j}t^{2 j}

.

(1) implies that

t ∂

∂t logζ(G,u,t)=Tr

−t ∂

∂t log(I−tA1+(1−u)(Q+uI)t²)

+Tr(Q−I) (1−u)²t² 1−(1−u)²t²

=Tr

−t ∂

∂t log

I−tA1+(1−u)(Q+uI)t²

−t ∂

∂tlog(1−(1−u)²t²)^Tr(Q−I)/2. Both functions are 0 at t =0, and so

logζ(G,u,t)= −Tr(log(I−tA1+(1−u)(Q+uI)t²))

−log(1−(1−u)²t²)^Tr(Q−I)/2.

Hence the equality Tr(log(I−B))=log det(I−B) implies that

ζ(G,u,t)=(1−(1−u)²t²)^−(m−n)det(I−tA1+(1−u)(Q+uI)t²)⁻¹.

3. A proof of the first formula in Theorem 2

We give a proof of the first formula in Theorem 2. The argument is an analogue of the method of Bass [3].

Let G be a connected graph with n vertices and m unoriented edges. Futhermore, let V (G)= {v1, . . . , vn}and R(G)= {e1, . . . ,em,em+1, . . . ,e2m}such that em+i =e_i⁻¹(1≤

i ≤m). Let B⁺=(B⁺_i,j)_1≤i≤2m;1≤j≤nbe the 2m×n matrix defined as follows:

(B⁺)i,j :=

1 if t(ei)=vj, 0 otherwise.

Furthermore, we define the 2m×n matrix B⁻=(B⁻_i,j)1≤i≤2m;1≤j≤nas follows:

(B⁻)i,j :=

1 if o(ei)=vj, 0 otherwise.

We denote by^tC the transpose of a matrix C. Then we have

B^+tB⁻=B (4)

and

tB⁻B⁺=A(G). (5)

Futhermore,

tB⁺B⁺=D. (6)

Now we set J=

0 Im

Im 0

and

T=B−J.

Then we have

B^+tB⁺=TJ+I2m. (7)

We introduce two (2m+n)×(2m+n) matrices as follows:

L=

(1−(1−u)²t²)In −^tB⁻+(1−u)t^tB⁺

0 I_2m

, M=

In tB⁻−(1−u)t^tB⁺ tB⁺ (1−(1−u)²t²)I2m

.

By (5) and (6), we have

LM=

(1−(1−u)²t²)In−t^tB⁻B⁺+(1−u)t^2tB⁺B⁺ 0

tB⁺ (1−(1−u)²t²)I_2m

=

(1−(1−u)²t²)In−tA(G)+(1−u)t²D 0

tB⁺ (1−(1−u)²t²)I2m

.

By (4) and (7),

ML=

(1−(1−u)²t²)In 0

t(1−(1−u)²t²)B⁺ −tB^+tB⁻+(1−u)t²B^+tB⁺+(1−(1−u)²t²)I2m

=

(1−(1−u)²t²)In 0

t(1−(1−u)²t²)B⁺ (I_2m−t(T+uJ))(I_2m−(1−u)tJ)

.

Here, note that J²=I2mand T+uJ=B−(1−u)J.

Since det(LM)=det(ML), we have (1−(1−u)²t²)^2mdet

In−tA(G)+(1−u)(D−(1−u)In)t²

=(1−(1−u)²t²)ⁿdet(I_2m−t(B−(1−u)J)) det(I_2m−(1−u)tJ). But,

det(I_2m−(1−u)tJ)=det

Im (1−u)tIm

0 Im

det

Im −(1−u)tIm

−(1−u)tIm Im

=det

(1−(1−u)²t²)Im 0

∗ Im

=(1−(1−u)²t²)^m.

Therefore it follows that

(1−(1−u)²t²)^2mdet(In−tA(G)+(1−u)(D−(1−u)In)t²)

=(1−(1−u)²t²)^m+ndet(I_2m−t(B−(1−u)J)).

Hence

det(I2m−t(B−(1−u)J))

=(1−(1−u)²t²)^m−ndet(In−tA(G)+(1−u)(D−(1−u)In)t²).

Acknowledgment

We would like to thank Professor A. Munemasa and the referees for valuable comments and suggestions.

References

1. S.A. Amitsur, “On the characteristic polynomial of a sum of matrices,” Linear and Multilinear Algebra 8 (1980), 177–182.

2. L. Bartholdi, “Counting paths in graphs,” Enseign. Math. 45 (1999), 83–131.

3. H. Bass, “The Ihara-Selberg zeta function of a tree lattice,” Internat. J. Math. 3 (1992), 717–797.

4. R. Bowen and O. Lanford, “Zeta functions of restrictions of the shift transformation,” Proc. Symp. Pure Math.

14 (1970), 43–50.

5. H. Davenport, Multiplicative Number Theory, Springer-Verlag, New York, 1981.

6. D. Foata and D. Zeilberger, “A combinatorial proof of Bass’s evaluations of the Ihara-Selberg zeta function for graphs,” Trans. Amer. Math. Soc. 351 (1999), 2257–2274.

7. R.I. Grigorchuk, “Symmetrical random walks on discrete groups,” in “Adv. Probab. Rel. Top.” D. Griffeath, (Ed.) Vol. 6, M. Dekker 1980, 285–325, pp. 132–152.

8. K. Hashimoto, “Zeta Functions of Finite Graphs and Representations of p-Adic Groups,” Adv. Stud. Pure Math. Vol. 15, pp. 211–280, Academic Press, New York, 1989.

9. K. Hashimoto, “On the zeta- and L-functions of finite graphs,” Internat. J. Math. 1 (1990), 381–396.

10. K. Hashimoto, “Artin-type L-functions and the density theorem for prime cycles on finite graphs,” Internat.

J. Math. 3 (1992), 809–826.

11. Y. Ihara, “On discrete subgroups of the two by two projective linear group over p-adic fields,” J. Math. Soc.

Japan 18 (1966), 219–235.

12. M. Kotani and T. Sunada, “Zeta functions of finite graphs,” J. Math. Sci. U. Tokyo 7 (2000), 7–25.

13. S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, MA, 1970.

14. A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs,” Combinatorica 8 (3) (1988), 261–277.

15. S. Northshield, “A note on the zeta function of a graph,” J. Combin. Theory Ser. B 74 (1998), 408–410.

16. D. Ruelle, Dynamical Zeta Functions for Piecewise Monotone Maps of the Interval, CRM Monograph Series Vol. 4, Amer. Math. Soc., Providence, RI, 1994.

17. A. Selberg,“Harmonic analysis and discontinuous groups in weakly symmetric Riemannian spaces with applications to Dirichlet series,” J. Indian Math. 20 (1956), 47–87.

18. J.-P. Serre, Trees, Springer-Verlag, New York, 1980.

19. H.M. Stark and A.A. Terras, “Zeta functions of finite graphs and coverings,” Adv. Math. 121 (1996), 124–165.

20. T. Sunada, “L-Functions in Geometry and Some Applications,” in “Lecture Notes in Math.” Vol. 1201, pp.

266-284, Springer-Verlag, New York, 1986.

21. T. Sunada, “Fundamental Groups and Laplacians” (in Japanese), Kinokuniya, Tokyo, 1988.

22. A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge Univ. Press, Cambridge (1999).

23. A.B. Venkov and A.M. Nikitin, “The Selberg trace formula, Ramanujan graphs and some problems of math- ematical physics,” St. Petersburg Math. J. 5(3) (1994), 419–484.