Ihara zeta function( 2nd part )

In this post I shall continue with some of the properties of the Ihara zeta function.
Allow me to say a bit more for the complex nature of Ihara’s zeta function. Since Ihara zeta function is function of complex variable and to be more specific a power series in the complex variable { u }, then it must have non-negative coefficients. So from the classical theorem of Landau, the product and the series defining Ihara zeta function will converge absolutely in a circle u smaller than { R_X } and will have a singularity at { u = R_X }.
For those who don’t have the time to search for Landau’s theorem, I state it here copying it from Tom Apostol’s analytic number theory book:

Theorem 1 {Landau’s theorem concerning Dirichlet series having non-negative coefficients}

Let { F(s) } be represented in the half-plane { \sigma > c } by the Dirichlet series

{F(s)= \sum_{n=1}^\infty \dfrac{f(n)}{n^s}, }

where { c } is finite, and assume that { f(n) \geq 0 } for all { n \geq n_0 }. If { F(s) } is analytic in some disk about the point { s = c }, then the Dirichlet series converges in the half-plane { \sigma > c - \epsilon } for some { \epsilon > 0 }. Consequently, if the Dirichlet series has a finite abscissa of convergence { \sigma_c }, then { F(s) } has a singularity on the real axis at points { s = \sigma_c }.

Another point I want to make, is that Ihara zeta function can determine the structure of a graph. To see this, let’s begin with the following lemma.

Lemma 2

{ Z_G(u) } determines i) if { G } is bipartite and ii) if { G } cyclic.

Before we start presenting the proof can we see why is this true? Ok let’s take a simple case where our graph is a n-cycle i.e. a cyclic graph of { n } vertices. I am sure you can all imagine that such a graph has two prime walks(one for each ‘direction’) of length { n } (you might want to draw it on a piece of paper and apply the prime walk definition). So immediately we can say that { Z_G(u) = (1 + u^n + u^{2n} \dots )^2 }. Here is a first connection, a very simple Ihara zeta function of a cyclic graph. A final thought before the proof is that a bipartite graph has a very common property concerning its closed walks(can you guess which one?) , so having in mind that Ihara zeta function is defined over prime walks (which are closed walks), we may have a connection with whether a graph is bipartite or not. Lets state now our proof.


i) { \Rightarrow } {G } is nonbipartite, so { G } contains an odd cycle { C} which represents a prime walk of odd degree.
{ \Leftarrow } If { G } is bipartite, then every closed walk has even degree, and hence every prime walk has even degree.
Now if we consider that { Z_G(u) } is an Euler product i.e. { Z_G(u) = \prod_C ( 1 +u^{deg(C)} + u^{2deg(C)} + u^{3deg(C)} \dots ) }, we can see that { G } does not contain a prime walk of odd degree if and only if an odd power of { u } appears in the previous power series. So, to put all pieces together, { G } is not bipartite if and only if an odd power of { u } appears in the power series { Z_G(u) }. Note that from the Bass formula, { Z_G(u)^{-1} } is a polynomial so we can just look up for any odd power of { u } in { Z_G(u)^{-1} }.

ii) As we said in our remarks before our proof we can say that { G } is a { n - cycle } if and only if { Z_G(u) = ( 1+ u^n + u^{2n} \dots )^2 }.

{ \Rightarrow } It is trivial if compute the prime walks of a { n - cycle }. { \Leftarrow } If { Z_G(u) = ( 1+ u^n + u^{2n} \dots )^2 } then it has two prime walks of length { n } which implies that either { G } is { n-cycle } or { G } is a linear graph of length { n }. But as we said in our previous post our assumption that { G } has minimum degree at least 2, forces us to choose the { n-cycle } .


Note: A linear graph is a graph with the form of a line, i.e { n + 1 } vertices connected by { n } edges in this way: { u_1 } to { u_2}, {u_2} to { u_3 } , { \dots } , { u_n } to { u_{n+1} }.

Now lets state the following theorem.

Theorem 3

Suppose that { G } is connected graph with minimum degree at least 2. Let { d } be the number of times { 1 - u^2 } divides { det(I-Au-Qu^2) }. Then

{ d = \begin{cases} 0 & \text{if G is nonbipartite} \\ 1 & \text{if G is bipartite but not an 2n cycle} \\ 2 & \text{if G is a 2n cycle} \end{cases} }

Exercise: Prove the following theorem:

Theorem 4

Let { G } be a connected graph with minimal degree at least 3. Then it can be determined from the Ihara zeta function whether { G } is
i) not bipartite
ii) bipartite but not cyclic, or
iii) bipartite and cyclic,
and in these cases the vertex number { n } of { G } is given by
i) { n = e - \delta }
ii) { n = e - \delta + 1 }
iii) { n = e - \delta + 2 }
where { \delta } is the number of times { 1 - u^2 } divides { Z_G(u)^{-1} } and { e } is the number of edges of { G }.

Hint: Use the previous theorem and lemma.

The references remain the same as in my previous post, but I would like to motivate you to explore the book Zeta functions of Graphs, a Stroll through the Garden by Audrey Terras and of course this book here by Reinhard Diestel which will strongly accompany you to your explorations in graduate level graph theory.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: