ZETA FUNCTIONS. NO.11

YOSHIFUMI TSUCHIMOTO

12. Zeta function of graphs.

12.1. Zeta functions of directed graphs.

Definition 12.1. A directed graph (digraph) is a pair X^{o} = (V^{o}, E^{o}) of:

• a set V^{o}, whose elements are called vertices or nodes,

• a set E^{o} called directed edges.

• two maps called “source”, “target” from E^{o} to V^{o}.

Let X^{o} = (V^{o}, E^{o}) be a directed graph. For each positive integer m, we let N_{m} to be the number of admissible closed paths in X^{o}. Then we put

Z_{X^{o}}^{o}(T) = exp (∑ \frac{1}{m}N_{m}T^{m})

We define Perron Frobeinus operator L_{X^{o}} : C(V^{o}) → C(V^{o}) to be

L_{X^{o}}(f)(x) = ∑_{\begin{matrix}e∈E^{o} \\ source(e)=x \end{matrix}} f(target(e)).

Proposition 12.2.

Z_{X^{o}}^{o}(T) = \frac{1}{det(1 − T · L_{X^{o}})}

Exercise 12.1. Let (M, φ) be a dinamical system of a finite set M. Is it possible to define a directed graph X = (M, E) such that its zeta function Z_{X} coincides with the zeta function of the dinamical system (M, φ)? (Compare the Perron Frobenius matrix L_{X} with ‘the pull back matrix’ P_{φ}.)

12.2. Ihara zeta function.

Definition 12.3. A graph (undiracted graph) is a pair X = (V, E) of:

• a set V, whose elements are called vertices or nodes,

• a set E called directed edges.

• a map called “(s,t)”, from E to V × V/𝔖_{2}.

YOSHIFUMI TSUCHIMOTO

Let X = (V, E) be a graph. The Ihara zeta function of X is defined by

Z(u) = ∏_{𝔭∈P}(1 − u^{length(𝔭)})^{−1},

where P denotes the set of prime cycles in X We define the adjacency operator A as

A(f)(x) = ∑_{\begin{matrix}e∈E \\ source(e)=x \end{matrix}} f(target(e)) = ∑_{y∈V} # \{ \begin{matrix}e ∈ E; \\ (s, t)(e) = (x, y) \end{matrix}\} f(y).

We also define the ‘degree operator’ D as:

D(f)(x) = deg(x)f(x)

where the degree deg(x) of x ∈ V is defined as

deg(x) = #{e ∈ E; source(e) = x}.

Theorem 12.4.

Z(u) = (1 − u^{2})^{χ(X)} det(I − uA + u^{2}(D − I))^{−1}

where χ(X) is the euler number of X.

12.3. directed Line graph associated to a graph. Let X = (V, E) be a graph. Then we define a directed graph (X_{L} = (V_{L}, E_{L}) called line graph of X as follows:

(1) V_{L} = E

(2) E_{L}^{o} = {(e_{1}, e_{2}) ∈ E × E; target(e_{1}) = source(e_{2})., ē_{1} ≠ e_{2}}.

Lemma 12.5.

det_{C(E)}(1 − u · L_{X_{L}}) = (1 − u^{2})^{−χ(X)} det_{C(V)}(I − uA + u^{2}(D − I))

Reference:

Motoko Kotani and Toshikazu Sunada, Zeta functions of finite graphs, J.Math.Sci.Univ.Tokyo 7(2000) 7-25