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.

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 }$ .

$\Box$

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.