% Date: Wed, 13 Jan 1999 18:54:41 -0800 (PST)
% From: Fan Chung Graham <fan@euclid.ucsd.edu>

%cover.tex
\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\setlength{\textwidth}{6in}
\setlength{\textheight}{9in}
\setlength{\evensidemargin}{0in}
\setlength{\oddsidemargin}{0in}
\setlength{\footskip}{.5in}
\setlength{\topmargin}{-\headheight}
\setlength{\parskip}{8pt}
\newtheorem{theorem}{Theorem}
\renewcommand{\thetheorem}{\arabic{theorem}}
\newtheorem{cor}{Corollary}
\renewcommand{\thecor}{\arabic{cor}}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newcommand{\LL}{{\mathcal L}}
\newcommand{\BLL}{{\mathbf L}}
\newcommand{\Sum}{\displaystyle\sum}
\newcommand{\Int}{\displaystyle\int}
\newcommand{\Frac}{\displaystyle\frac}
\newcommand{\ghat}{\mbox{$\hat{G}$}}
\newcommand{\ip}{\mbox{$i^{\prime}$}}
\newcommand{\lh}{\mbox{$\hat{L}$}}
\newcommand{\SLS}{\mbox{$T^{- 1/2}L T^{-1/2}$}}
\newcommand{\qedsymbol}{\mbox{$\square$}}
\newbox\qedbox \setbox\qedbox\hbox{\quad\qedsymbol}%
\newbox\lineqedbox \setbox\lineqedbox\hbox to\hsize{\hfill\qedsymbol}%
\newcommand{\qed}{\ifhmode\unskip\nobreak\fi\hfill
  \discretionary{\null}{\copy\lineqedbox}{\copy\qedbox}}
\newcommand{\proof}{\noindent{\it Proof:~~~}}
\baselineskip 24pt
\renewcommand{\today}{}
\pagestyle{myheadings}\markboth{\hfill
{\sc the electronic journal of combinatorics 6 (1999), \#R12}}
{{\sc the electronic journal of combinatorics 6 (1999), \#R12}\hfill}
\begin{document}
\thispagestyle{empty}
\title{Coverings, heat kernels and spanning trees}

\author{Fan Chung $^{\dagger}$
\thanks{Research supported in part by NSF Grant No. DMS 98-01446}
\\
University of Pennsylvania\\
Philadelphia, Pennsylvania 19104 \\
chung@hans.math.upenn.edu\\
\and S.-T. Yau
\footnote{Research supported in part by NSF Grant No. DMS 95-04834}
\\
Harvard University
\\
Cambridge, Massachusetts 02138\\
yau@math.harvard.edu}
\date{\today}{}
\maketitle

\begin{center}
Submitted: May 1, 1998; Accepted: December 12, 1998.\\
\vspace{.1in}
AMS Subject Classification: 05C50, 05Exx, 35P05, 58G99.
\end{center}
\begin{abstract}
We consider a graph $G$ and a covering $\tilde{G}$
of  $G$ and we study 
the relations of their eigenvalues and  heat kernels.
We evaluate the heat kernel for an infinite $k$-regular tree
and we examine the heat kernels
for general $k$-regular graphs.
In particular, we show that a $k$-regular graph on $n$ vertices 
has at most 
\[ (1+o(1))  \frac {2\log n}{kn \log k} \left( \frac{(k-1)^{k-1}} {(k^2-2k)^{k/2-1}}\right)^n \]
spanning trees, which is 
best possible within a constant factor.

\end{abstract}
%\setlength{\baselineskip}{1.5\baselineskip}
\section{Introduction}
We consider a weighted undirected graph $G$ (possibly with loops) which 
has a vertex set $V=V(G)$ and
a weight function
$w : V \times V \rightarrow {\mathbb R}$ satisfying
\[w (u,v) = w(v,u) 
~~\mbox{and}
~~ w(u,v) \geq  0 .\]
If $w(u,v) > 0$, then we say  $\{u,v\} $ is an edge
and $u$ is adjacent to $v$.
A simple graph is the special case where all
the weights are $0$ or $1$ and $w(v,v)=0$ for all $v$.
In this paper, by a graph we mean a weighted graph unless specified.

The degree $d_v$ of a vertex $v$ is 
defined to be:
$$ d_v = \Sum_u w(u,v). $$
%$$ \vol~G = \Sum_v d_v. $$
A graph is regular if all its degrees are the same.
For a vertex $v$ in $G$,  the neighborhood $N(v)$ of $v$ consists
of all vertices adjacent to $v$.

This paper is organized as follows: In Section 2, we define 
a covering of a graph and give several examples. In Section 3, 
we give the definitions for the Laplacian, eigenvalues
and the heat kernel of a graph. In Section 4, we consider the relations between
the eigenvalues of a graph and the eigenvalues of its covering.
In particular, we give a proof for determining
the eigenvalues
and their multiplicities of a strongly cover-regular graph $G$ from
the eigenfunctions of the (smaller) graph covered by $G$.
In Section 5, we derive the heat kernel of an infinite
$k$-regular tree. Then in Section 6, we consider
heat kernels of some $k$-regular graphs.
In Section 7, we consider the relations between the trace of the heat kernel
and the number of spanning trees in a graph.
In Section 8, we
 focus on an old problem of
determining the maximum number of spanning trees in
a $k$-regular graph.
We consider the zeta function
of a graph and we improve the upper and lower bounds for the 
maximum number
of spanning trees in a $k$-regular graph on $n$ vertices.
  
\section{The coverings of graphs}
Suppose we have two graphs $\tilde{G}$ and $G$. We say $\tilde{G}$ is a 
{\it covering} of $G$ (or $G$ is covered by $\tilde{G}$)
if there is a mapping $\pi: V(\tilde{G})
\rightarrow V(G)$ satisfying the following two properties:
\begin{description}
%\item[(i)]
%$\pi$ is {\it edge-preserving}, i.e., if 
%$x$ is adjacent to $ y$ in $\tilde{G}$, then
% $\pi(x)$ is adjacent to $ \pi(y)$ in $G$.
\item[(i)]
There is an $m \in {\mathbb R}^+ \cup \{ \infty \}$, called the {\it index } of 
$\pi$, such that for 

%For a simple graph, each edge $e$ in $G$, the number of 
%edges in $\tilde{G}$ being mapped to $\pi(e)$ is independent of $e$
%and is equal to $m$. I. e., for every $\{u,v\} \in 
%E(G)$, we have
% \[ |\{ \{x,y\} \in E(\tilde{G}): \pi(x)=u , \pi(y)=v\}| =m. \]

$u, v \in V(G)$, we have
\[ \sum_{\substack{ x \in \pi^{-1}(u) \\ y \in \pi^{-1}(v)}}
w(x,y) = m~w(u,v). \]
\item[(ii)]
For $x,y \in V(\tilde{G})$ 
with $\pi(x)=
\pi(y)$ and $v \in V(G)$,
% and $v$ adjacent to $\pi(x)$ in $G$,
 we have
%, for a simple graph,
%\[ |N(x) \cap \pi^{-1}(v)|=|N(y) \cap \pi^{-1}(v)|. \]
%And for a weighted graph, we have
\[ \sum_{z \in \pi^{-1}(v)} w(z,x) =
 \sum_{z' \in  \pi^{-1}(v)} w(z',y). \] 
\end{description}

\noindent
{\it Remark 1}:
For  simple graphs $G$ and $\tilde{G}$, (i) is equivalent to
\\
(i')
For every $\{u,v\} \in 
E(G)$, we have
 \[ |\{ \{x,y\} \in E(\tilde{G}): \pi(x)=u , \pi(y)=v\}| =m. \]
And (ii) is equivalent to\\
(ii')
For $x,y \in V(\tilde{G})$ 
with $\pi(x)=
\pi(y)$,
 and $v$ adjacent to $\pi(x)$ in $G$,
 we have
\[ |N(x) \cap \pi^{-1}(v)|=|N(y) \cap \pi^{-1}(v)|. \]
In other words, $\pi^{-1}$ defines a so-called {\it equitable } partition of
$V(\tilde{G})$ which has been studied extensively in the literature.
The reader is referred to
Cvetkovi\'c, Doob and Sachs \cite{cds}, McKay \cite{mck9},
Godsil and McKay \cite{gm}.

\noindent
{\it Example 1}: Suppose $\tilde{G} = C_{2n},$ the cycle on $2n$ vertices
 and $G=P_{n+1}$, the path on $n+1$ vertices.
The covering has index $2$ since each edge of $P_{n+1}$ is covered
by two edges of $C_{2n}$.

\noindent
{\it Example 2}:
% A graph $G$ is said to be {\it vertex
%transitive} if for any two vertices $u$ and $v$, there is
%a graph isomorphism $\varphi$ satisfying $\varphi(u)=v$.
A graph $\tilde{G}$ is 
said to be a {\it regular covering} of $G$ 
if for a fixed vertex $v$ in $V(G)$ and 
 for any vertex $x$ of $V(\tilde{G})$, 
$\tilde{G}$ is a covering of $G$ under a mapping  $\pi_x$
which maps $x$ into $v$. 
In addition, if $\pi_x^{-1}$ is just $x$,
we say $\tilde{G}$ is a {\it strong regular covering} of $G$.
A graph $G$ is said to be
 {\it distance regular}
if $G$ is a strong regular covering of a (weighted) path $P$
 (with possible non-zero $w(v,v)$).
For example, for a vertex $x $ in $V(G)$, we can consider
a mapping $\pi_x$   so that 
all vertices $y$ at distance $i$ from $x$ are mapped
to the $i$-th vertex of $P$.
This definition is equivalent to
the definition of distance regular graphs, given by
Biggs \cite{biggs}. 

%\noindent
%{\it Example 3:}  
% A graph $G$ is said to be {\it vertex
%transitive} if for any two vertices $u$ and $v$, there is
%a graph isomorphism $\varphi$ satisfying $\varphi(u)=v$.

\noindent
{\it Example 3:}  Let $T_k$ denote an infinite $k$-tree. It is
not hard to check that  $T_k$ is a covering
of a $k$-regular graph $G$. 
More on this will be discussed in Sections 5 and 6.

We note that in a covering $\tilde{G}$ of $G$,
the vertices $v$ in $G$ can have preimages $\pi^{-1}(v)$ of different
sizes (as in Example 2). In addition, the degrees of vertices in $\tilde{G}$  
or $G$ are not
necessarily the same.
Nevertheless, there is a certain uniformity  in the preimage of a vertex
as illustrated in the following facts:
\begin{fact}
Suppose $\tilde{G}$ is a covering of $G$ under $\pi$ with index
$m$. Then for 
%an edge $\{u,v\}$ in  $G$ and 
$x \in \pi^{-1}(v)$, we have
%\[ |\pi^{-1}(v)| \cdot |N(x) \cap \pi^{-1}(u)| = m \]
%and for weighted graphs, we have
\[
 |\pi^{-1}(v)|
 \sum_{z \in \pi^{-1}(u)} w(z,x) = 
m w(u,v). \]
\end{fact}
The proof follows from (i) and (ii). For a simple graph, Fact 1 implies
\[ |\pi^{-1}(v)| \cdot |N(x) \cap \pi^{-1}(u)| = m. \]
As an immediate consequence, we have
\begin{fact}
Suppose $\tilde{G}$ is a covering of $G$ under $\pi$ with edge multiplicity
$m$. Then for 
 $x,y \in \pi^{-1}(v)$, we have
\[d_x = d_y. \]
\end{fact}
\section{The Laplacian and the heat kernel of a graph}
For a weighted graph $G$ on $n$ vertices associated with a weight function $w$,
we consider
the combinatorial Laplacian $L$ of $G$.
\[L (u,v) = \left\{ \begin{array}{ll}
                                   d_v - w(v,v) & \mbox{ if $u = v$,} \\
                                   -w(u,v)  & \mbox{ if $u$ and $v$ are
                                   adjacent,}\\
                                   0 & \mbox{ otherwise. }
                                  \end{array}
                       \right. \]
In particular, for a function $f: V \rightarrow {\mathbb R}$, we have
 \[  Lf(v) =\Sum_y
(f(v)-f(u))w(u,v). \]

Let $T$ denote the diagonal matrix with the $(v,v)$-th entry
having value $d_v$. The (normalized)  {\it Laplacian}
of $G$ is defined to be
\[\LL (u,v) = \left\{ \begin{array}{ll}
                                   1 - \Frac{w(v,v)}{d_v}& \mbox{ if $u = v$,
and $d_v \not = 0$,} \\[3mm]
                                   -\Frac{w(u,v)}{\displaystyle\sqrt{d_u d_v}}
 & \mbox{ if $u$ and $v$ are adjacent,}\\[3mm]
                                   0 & \mbox{ otherwise.}
                                  \end{array} \right. \]
In other
words, we have
\[ \LL=T^{-1/2}LT^{-1/2}. \]
For a $k$-regular graph, we have
\[ {\mathcal L} = I - \frac 1 k A \]
where $A$ is the adjacency matrix.

We denote the eigenvalues of $\LL$ by $0=\lambda_0 \leq \lambda_1\dots
\leq \lambda_{n-1}$ (which are sometimes called the eigenvalues of $G$). 
If $G$ is connected, we have $0 < \lambda_1$.  
The reader is referred to \cite{ch0} for various
properties of eigenvalues of a graph.

In this paper, we mainly deal with connected graphs.
Let $g$ denote an eigenfunction of $\LL$ associated with eigenvalue
$\lambda$. It is sometimes convenient to consider $f = T^{-1/2} g$,
called the {\it harmonic eigenfunction}, which satisfies, for 
every vertex $v$ of $G$,
\[ \Sum_u (f(v)-f(u))w(u,v)= \lambda d_v f(v). \]

For a graph $G$, we consider
the heat kernel $h_t$, which is defined for
$t \geq 0$ as follows:

\begin{eqnarray}
\label{ex1}
h_t & = & \Sum_i e^{- \lambda _it} P_i \nonumber\\
& = & e^{-t \mathcal L} \nonumber \\
& = & I - t \LL + \frac{t^2}{2} \LL^2 - \ldots
\end{eqnarray}
where $P_i$ denotes the projection into the eigenspace associated
with eigenvalue $\lambda_i$.
In particular, $$h_0 = I.$$
and
$h_t$ satisfies the heat equation
$$ \frac{\partial h_t}{\partial t} = -\LL h_t. $$
For any two vertices $x,y \in V$, we have
\[ h_t(x,y)= \Sum_i e^{-\lambda_i t} \phi_i(x) \phi_i(y) \]
where $\phi_i$'s are orthonormal eigenfunctions of the Laplacian $\mathcal L$.

In particular, the trace of $h_t$ satisfies
\begin{eqnarray*}
 {\mathit Tr} h_t &=& \sum_x h_t(x,x)
\\
&=& \sum_i e^{-\lambda_i t}.
\end{eqnarray*}

\section{Eigenvalues of a graph and its covering }
If $\tilde{G}$ is a covering of $G$, their eigenvalues are intimately related.
Namely, the spectrum of a large
(covering) graph can often be determined from a small (covered) graph. 
This provides a simple
method for determining the spectrum of 
certain families of graphs.
Such approaches have long been 
studied in the literature.  
Here we will list several facts which will be used later.
The proofs of some of these facts  
can be found in Godsil and McKay \cite{gm}
(in which the definitions
involve $(0,1)$ matrices but the proofs often can be adapted for 
general weighted graphs). We will sketch the proofs here for
the sake of completeness.

If $\tilde{G}$ is a covering of $G$, 
we can ``lift" the harmonic eigenfunction $f$ of $G$ to $\tilde{G}$ by defining,
for each vertex $x$ in $\tilde{G}$, $f(x)=f(u)$  where $u =\pi(x)$.
{}From definition (ii) of covering, we have
\begin{eqnarray*}
\sum_y (f(x)-f(y))w(x,y) &=&
 \sum_v (f(u)-f(v)) w(u,v)~
\\
&=& \lambda d_x.
\end{eqnarray*}
Therefore we have
\begin{lemma}
\label{ma1}
If $\tilde{G}$ is a covering of $G$, then an eigenvalue of $G$ is
an eigenvalue of $\tilde{G}$.
\end{lemma}

For each $x \in \pi^{-1}(v)$,
\[ \sum_{\substack{ y }}(f(x)-f(y))w(x,y)=\lambda f(x) d_x. \]
By summing over $x $ in $\pi^{-1}(v)$, we have
\[\sum_{x \in \pi^{-1}(v)} \sum_{\substack{ y } } 
(f(x)-f(y))w(x,y)=
\lambda \sum_{x \in \pi^{-1}(v)} f(x) d_x. \]
 We define
the induced mapping of $f$ in $G$, denoted by $\pi f~:~V(G) \rightarrow {\mathbb R}$
by
\[ (\pi f )(v)= \sum_{x \in \pi^{-1}(v)} \frac{f(x) d_x}{ d_v}. \]
Then, for $g = \pi f$,  we have
\[ \sum_{\substack{ u  }} (g (v)- g (u))w(u,v)= \lambda  g(v) d_v. \]
If $g$ is nontrivial, $\lambda$ is
an eigenvalues of $\tilde{G}$. 
Thus we have shown the following:
\begin{lemma}
\label{ma2}
Suppose $\tilde{G}$ is a covering of $G$ and.  
If
a harmonic eigenfunction $f$ of $\tilde{G}$,
associated with an eigenvalue $\lambda$, has
a nontrivial image in $G$, then 
$\lambda$ is also an eigenvalue for $G$.
\end{lemma}

%A graph $G$ is said to be {\it distance transitive} 
%if for any four vertices $x,y,z,w$ with $d(x,y)=d(z,w)$, there is
%an automorphism $\rho$ such that $\rho(x)=z$ and $\rho(y)=w$.
%A distance transitive graph is distance regular.
%Distance regular graphs
%and distance transitive graphs have been extensively studied in 
%the literature (see  \cite{biggs}). 
%Here we give a slightly more general (and simpler ) treatment using
%coverings of graphs.

\begin{lemma}
\label{ma3}
Suppose $\tilde{G}$  is a strong regular covering
of $G$. 
Then, $\tilde{G}$ and $G$ have the same eigenvalues.
\end{lemma}
\proof
For any nontrivial harmonic
eigenfunction $f$ of $\tilde{G}$ we can choose $v$ to be a vertex with 
nonzero value of $f$. The induced mapping of $f$ in $G$ has a nonzero value
at $v$ and therefore is a nontrivial harmonic eigenfunction for $G$. 
{}From Lemma \ref{ma2}, we see that any eigenvalue of $\tilde{G}$ 
is an eigenvalue
of $G$. By Lemma \ref{ma1}, we conclude that $\tilde{G}$ and $G$ have the same
eigenvalues.
\qed

Therefore the eigenvalues of a covering graph $\tilde{G}$
 can
 be  determined by computing the eigenvalues of a smaller graph $G$.
However, the multiplicities for the eigenvalues in $\tilde{G}$ are, in general, different from those in 
$G$ since, for example, $\tilde{G}$ and $G$ can have different numbers of 
vertices. Nevertheless, the multiplicities of eigenvalues of $\tilde{G}$
and $G$ are related through the relations of 
their heat kernels.
\begin{lemma}
\label{ma4}
Suppose $\tilde{G}$ is a covering of $G$.
Let $\tilde{h}_t$ and $h_t$ denote the heat kernels of $\tilde{G}$ and $G$,
respectively. Then we have 
 \[ \sum_{x \in \pi^{-1}(u)}
\sum_{y \in \pi^{-1}(v)} \tilde{h}_t(x,y)=
\sqrt{| \pi^{-1}(u)| \cdot | \pi^{-1} (v)|}
h_t(u,v). \]
\end{lemma}
\proof
We note that 
the heat kernel $h_t(u,v)$ satisfies
\[ h_t(u,v) = e^{-t} \Sum_r S_r(u,v) \frac {t^r}{r!} \] 
where $S_r$ is the sum of weights of all walks of length $r$ joining
$u$ and $v$. (Here a walk $p_r$ is a sequence of vertices $u_0,\dots,u_r$
such that $u_i=u_{i+1}$ or $\{u_i,u_{i+1}\}$ is an edge. The weight
of a walk is the product of $w(u_i,u_{i+1})/ \sqrt{d(u_i) d(u_{i+1})}$, 
for $i=0,\dots,r-1$.)
We want to show that the total  weights of the paths in $\tilde{G}$
lifted from $p_r$ (i.e., whose image in $G$ is $p_r$)  is 
exactly the weight of $p_r$ in $G$ multiplied by 
$\sqrt{| \pi^{-1}(u_0)| \cdot | \pi^{-1} (u_r)|}$.
Let $p_{r-1}$ denote the walk $u_0,\dots,u_{r-1}$. Suppose
$u_{r-1} \not = u_r$ (The other case is easy). 
For each path $\tilde{p}_{r-1}$ lifted from $p_{r-1}$, its extensions
to paths lifted from $p_r$ has total weights
\begin{eqnarray*}
&& w(\tilde{p}_{r-1}) \cdot  \Sum_{\substack{ z \in \pi^{-1}(u_r)
}} \frac{-w(u_{r-1},z)}{\sqrt{d(u_{r-1}) d(z)}}\\
&=& w(\tilde{p}_{r-1}) 
 \frac{-m w(u_{r-1},u_r)/|\pi^{-1}(u_{r-1})|}{\sqrt{m d(u_{r-1}) m d(u_r)/
(|\pi^{-1}(u_{r-1})|~~|\pi^{-1}(u_r)|)}}\\
&=& w(\tilde{p}_{r-1}) 
 \frac{- w(u_{r-1},u_r)}{\sqrt{ d(u_{r-1}) d(u_r)}}
\sqrt{\frac{|\pi^{-1}(u_r)|}{|\pi^{-1}(u_{r-1})|}}.
\end{eqnarray*}
By summing over all $\tilde{p}_{r-1}$, we have
 \[ \sum_{x \in \pi^{-1}(u)}
\sum_{y \in \pi^{-1}(v)} S_r(x,y)=
\sqrt{| \pi^{-1}(u)| \cdot | \pi^{-1} (v)|}
S_r(u,v). \]
Therefore, we complete the proof
of Lemma \ref{ma4}.
\qed

As a consequence of Lemma \ref{ma4}, we have
\begin{cor}
Suppose $\tilde{G}$ is a strong regular covering of $G$.
Let $\tilde{h}_t$ and $h_t$ denote the heat kernels of $\tilde{G}$ and $G$,
respectively. For $x \in \pi^{-1}(u)$, we have 
 \[ 
\sum_{y \in \pi^{-1}(v)} \tilde{h}_t(x,y)=
\sqrt{\frac{| \pi^{-1}(v)|}{ | \pi^{-1} (u)|}}
h_t(u,v). \]
\end{cor}
\begin{cor}
\label{ma5}
Suppose $G$ is a distance regular graph which
is a covering of a path $P$ with vertices $v_0, \dots, v_p$
where $p=D(G)$. 
Suppose $G$ and $P$ have heat kernels $\tilde{h}_t$ and $h_t$,
respectively.
For any two vertices $x$ and $y$ in $G$
with distance  $d(x,y)=r$, we have
\[ \tilde{h}_t(x,y)= \sqrt{|\pi^{-1}(u_r)|} h_t(v_0,v_r). \]
\end{cor}

\begin{theorem}
\label{t1}
Suppose $\tilde{G}$ is a strong regular covering 
of $G$. 
Let $v$ denote the vertex of $G$ with preimage in $\tilde{G}$
consisting of one vertex.
Then any eigenvalue $\lambda$ of $\tilde{G}$ has multiplicity 
\[ n \sum_i \frac{ \phi_i^2(v)}{ \| \phi_i \|^2}, \]
where 
 $n=|V(\tilde{G})|$ and 
$\phi_i$ 's span the eigenspace of $\lambda$ in $G$.
If the eigenvalue $\lambda$
has multiplicity $1$ in $G$ with eigenfunction $\phi$,
then the multiplicity
of $\lambda$ in $\tilde{G}$ is
\[ \frac{n \phi^2(v)}{ \| \phi \|^2}. \]
\end{theorem}
\proof
Suppose $\tilde{G}$ has heat kernel $H_t$ and $G$ has 
heat kernel $h_t$.
Since $\tilde{G}$ is a strong regular covering of $G$, we have
\begin{eqnarray*}
 Tr(\tilde{h}_t) &=& 
 \sum_{x \in V(\tilde{G})} H_t(x,x)\\
&=& n h_t(v,v)
\\
&=& n \sum_j e^{-t \lambda_j} \frac{ \phi_j^2(v) }{\| \phi_j \|^2}.
\end{eqnarray*}
Therefore, the multiplicity of $\lambda_j$ in $\tilde{G}$ is exactly
\[ \frac{n~ \phi^2_j(v) }{\| \phi_j \|^2} \]
if the multiplicity of $\lambda$ in $G$
is $1$ and . In general, the multiplicity of $\lambda$ in $ \tilde{G}$ is
\[ n \sum_i \frac{ \phi_i^2(v)}{ \| \phi_i \|^2} \]
where $\phi_i$ 's span the eigenspace of $\lambda$ in $G$.
\qed

As an immediate consequence of Theorem \ref{t1}, we have the following:
\begin{cor}
A distance regular graph $G$ with diameter $D$
has $D+1$ distinct eigenvalues $\lambda$'s  which are
the eigenvalues of a weighted path $P$ of length $D$.
(The weight of edge $\{v_i, v_{i+1}\}$ in $P$ is the number of
edges joining a vertex at distance $i$ from $x$ to a vertex at 
distance $i+1$ from $x$ for a fixed number $x$. The weight of
the loop $\{v_i, v_i\}$ is twice the number of edges with both
endpoints at distance $i$ from $x$.)
The multiplicity of $\lambda$ in $G$ is
\[ \frac{n \phi^2(x)}{ \|\phi \|^2} \]
where $n$ is the number of vertices in $G$
and $\phi$ is the eigenfunction of $\lambda$ of the Laplacian of $P$.
\end{cor}

\noindent
{\it Example 4:}
The Petersen graph $G$
is a covering for a path $P$ of $3$ vertices.
It is easy to check that $P$ has three eigenvalues $0,2/3,5/3$ with
eigenfunctions
$\phi_0=(\sqrt 3,\sqrt 6,\sqrt{18})$, $\phi_1=(\sqrt 3,1,-\sqrt 2)$
and $\phi_2=(\sqrt 6,-2 \sqrt 2,1)$, respectively. 
Using Lemma \ref{ma6}, we see
that eigenvalues $0,2/3,5/3$ have multiplicities $1,5,4$ in $G$,
respectively. 


\section{The heat kernel of $k-$trees}

Let $T_k$ (or $k$-tree, in short)
 denote an infinite $k-$regular tree.  
Let $T_{k,l}$ denote an $l-$level tree with a root at the 
$0-$th level.  The $l-$th level consists of the $k(k-1)^{l-1}$
vertices at distance $l$ from the root.  The infinite tree can
be viewed as taking the limit of $T_{k,l}$ as $l$ approaches
infinity.  

The heat kernel of $T_k$ plays a central role in examining
the
spectrum of any k-regular graph. 
To determine the heat kernel of $T_k$, we can use
the covering theorem in the previous section.
The study of eigenvalues and eigenfunctions of $T_k$ can be found
in 
many papers in the literature 
\cite{benson, br, fh, sarnak, sing}.
Here we will give a self-contained proof for establishing
the explicit formula for the kernel of the $k$-tree, for $k \geq 3$.
For the case of $k=2$, $T_2$ is just the infinite path.
This special case and its cartesian products were examined in \cite{cy1}.

$T_k$ can be regarded as a covering of the following weighted path
$P$. The vertex
of $P$ is $\{0,1,2,\ldots \}$. For $j >0$, the
edge joining $j-1$ to $j$ has weight $k(k-1)^{j-1}$.
the covering mapping $\pi$ is defined by assigning 
all vertices in the $j$-th level to vertex $j$ in $P$.   The Laplacian
$\LL$ for the weighted path has entries
\[ \LL (i,j)=	\left\{ \begin{array}{cl}
			1	&	\mbox{if $i=j$,}\\
			-\frac{1}{\sqrt{k}} & \mbox{if $(i,j)=(0,1)$
				or $(1,0)$,}\\
			-\frac{\sqrt{k-1}}{k} & \mbox{if $|i-j|=1$,
				$i,j \neq 0$,}\\
			0	&	\mbox{otherwise.}
			\end{array}
		\right.	\]
We observe that $\LL$ is quite close to $I-\frac{\sqrt{k-1}}{k} M$
where $M$ is the cyclic operator with $M(i,i+1)=M(i+1,i)= \frac{\sqrt{k-1}}
{k}$ for $i \geq 0$ and $0$, otherwise.
Intuitively, the eigenvalues of $T_{k}$ are just, for a fixed integer $l$,
\[1-\frac{2\sqrt{k-1}}{k} \cos \frac{ \pi j}{l}	~\mbox{for 
$j=1,\ldots ,l-1$} \]
in addition to the eigenvalues $0$ and $2$.

In order to examine the eigenvalues and eigenfunctions of $P$ explicitly,
we consider the following $l \times l$ matrix $\LL^{(l)}$, for $l \geq 3$:
\[ \LL^{(l)} = \left( \begin{array}{cccccc}
			1 & -\frac{1}{\sqrt{k}} & 0 & \cdots& \cdots & 0\\
			-\frac{1}{\sqrt{k}} & 1 &
-\frac{\sqrt{k-1}}{k} 
 & 0 & \cdots & 0 \\
			0 &
-\frac{\sqrt{k-1}}{k} & 1 & 
-\frac{\sqrt{k-1}}{k} 
& \cdots & 0 \\
  \cdots & \cdots & \cdots & \cdots & -\frac{\sqrt{k-1}}{k} & 0 
\\ 
0 & \cdots & \cdots & \cdots &1 &
-\sqrt{\frac{k-1}{k}}\\ 
			0 & \cdots & \cdots & \cdots &
-\sqrt{\frac{k-1}{k}}&1 
			\end{array} \right) \]
where
\[ \LL^{(l)} (i,j)=	\left\{ \begin{array}{cl}
			1	&	\mbox{if $i=j$},\\
			-\frac{1}{\sqrt{k}} & \mbox{if $(i,j)=(0,1)$
				or $(1,0)$,}\\
			-\frac{\sqrt{k-1}}{k} & \mbox{if $|i-j|=1$,
				$0 <i,j < l$,}\\
			-\sqrt{\frac{k-1}{k}} & \mbox{if $(i,j)=(l-1,l)$
or $(l,l-1)$,}\\
			0	&	\mbox{otherwise.}
			\end{array}
		\right.	\]
The eigenvalues of $\LL^{(l)}$ are $ 0,~ 2$ and
\[1-\frac{2\sqrt{k-1}}{k} \cos \frac{ \pi j}{l}	~\mbox{for 
$j=1,\ldots ,l-1$.} \]
The eigenfunction $\phi_0$ associated with eigenvalue $0$
is $\phi_0 = f_0 / \|f_0 \|$ where $f_0$ is defined as follows:\
\begin{eqnarray*}
f_0(0)& =&1, \\
f_0(p)&=&\sqrt{k(k-1)^{p-1}}, \mbox{~~~~~~~~~~~ ~~~~~ for $1 \leq p \leq l-1$},\\
f_0(l)&=&\sqrt{(k-1)^{l-1}}.
\end{eqnarray*}
The eigenfunction $\phi_l$ associated with eigenvalue $2$
is $\phi_l = f_l / \|f_l \|$ where $f_l$ is defined as follows:\
\begin{eqnarray*}
f_l(0)& =&1, \\
f_l(p)&=& (-1)^p\sqrt{k(k-1)^{p-1}}, \mbox{~~~~~~~~~~~ ~~~~~ for $1 \leq p \leq l-1$},\\
f_l(l)&=& (-1)^l\sqrt{(k-1)^{l-1}}.
\end{eqnarray*}

The eigenfunction $\phi_j$, for $j=1,\cdots,l-1 $, associated with eigenvalue 
$1-\frac{2\sqrt{k-1}}{k} \cos \frac{ \pi j}{l}$ is $f_j/\|f_j\|$ where

\begin{eqnarray*}
f_j(0)& = &\sqrt{\frac{k}{k-1}} \sin \frac{ \pi j}{l}, \\
f_j(p)&=& 
 \sin \frac{ \pi j(p+1)}{l}
 -\frac{1}{k-1}\sin \frac{ \pi j(p-1)}{l},
\mbox{~~~~~~~~~~ ~~~~~ for $1 \leq p \leq l-1$},\\
f_j(l)&=&-\frac{\sqrt {k}}{k-1} \sin 
 \frac{ \pi j}{l}.
\end{eqnarray*}
It is easy to compute, for $j=1,\cdots,l-1$,
\[ \| f_j \|^2 = \frac{l k^2}{2(k-1)^2} (1-\frac{4(k-1)}{k^2} \cos^2
\frac{ \pi j}{l}). \]
Therefore the heat kernel $h^{(l)}$ of $P^{(l)}$ satisfies
\begin{eqnarray*}
h^{(l)}(0,0) = \sum_{j=1}^{l-1} \frac
{ e^{-t(1-\frac{2\sqrt{k-1}
               }{k} \cos \frac{ \pi j}{l})
    }
 \sin^2 \frac{ \pi j}{l}
}
{
\frac{lk}{2(k-1)}(
1-\frac{4(k-1)}{k^2} \cos^2 \frac{ \pi j}{l})
}
+ \frac{1}{\| f_0 \|^2}
+ \frac{1}{\| f_l \|^2}.
\end{eqnarray*}
When $l$ approaches infinity, the heat kernel $h$ of $P$
satisfies:
\begin{eqnarray*}
h_t(0,0) = \frac{2k(k-1)}{\pi} \Int_0^{ \pi} 
\frac{
e^{-t(1-\frac{2\sqrt{k-1}}{k} \cos x)}
 \sin^2 x}
{k^2-4(k-1) \cos^2 x}
dx.
\end{eqnarray*}
In general, for $a \geq 1$, we have
\begin{eqnarray*}
h_t(0,a) =  \frac{2\sqrt{k(k-1)}}{\pi } \Int_0^{ \pi} 
\frac{e^{-t(1-\frac{2\sqrt{k-1}}{k} \cos x)} \sin x
 [(k-1)\sin (a+1) x-\sin(a-1)x]}
{k^2-4(k-1) \cos^2 x}
dx.
\end{eqnarray*}

For the infinite $k$-tree $T_k$, its heat kernel is denoted by $H_t$.
For two vertices $x,y$ in $T_k$, we will write $H_t(x,y)=
H_t(0,d(x,y))$ where $d(x,y)$ denotes the distance of $x $
and $y$ in $T_k$. In particular, $H_t(x,x)=H_t(0,0)$ for all
vertices $x$.
Using Lemma \ref{ma4} and the fact that the infinite $k$-tree is
a covering of $P$, we have the following:
\begin{theorem}
%\label{t1}
The heat kernel $H_t$ of the infinite $k$-tree satisfies
\begin{eqnarray*}
H_t(0,0)& =& \frac{2k(k-1)}{\pi} \Int_0^{ \pi} 
\frac{
e^{-t(1-\frac{2\sqrt{k-1}}{k} \cos x)}
 \sin^2 x}
{k^2-4(k-1) \cos^2 x}
dx
\\
H_t(0,a)& = & \frac{2}{\pi (k-1)^{a/2-1}} \Int_0^{ \pi} 
\frac{e^{-t(1-\frac{2\sqrt{k-1}}{k} \cos x)} \sin x
 [(k-1)\sin (a+1) x-\sin(a-1)x]}
{k^2-4(k-1) \cos^2 x}
dx.
\end{eqnarray*}
\end{theorem}
\begin{cor}
The heat kernel $H_t(0,0)$ of the infinite $k$-tree can be written as
\begin{eqnarray*}
 H_t(0,0) & =&
e^{-t} \sum_{r \geq 0} \sum_{j=0}^r \binom {2r}{j} \frac{2r-2j+1}{2r-j+1}
(k-1)^j (\frac t k)^{2r}\\
&=&
 \frac{2(k-1)}{k} \sum_{s \geq 0} (\frac{4(k-1)}{k^2})^{2s}
\frac{(2s-1)!!}{(2s+2)!!} \sum_{0 \leq j \leq s} \frac {t^2j}{(2j)!}
\end{eqnarray*}
where $m!! $ denotes the product of all numbers less than or equal to $m$
and having the same parity as $m$.
\end{cor}

We note that the first sum in the corollary above appeared in \cite{mckay}.
We remark that the heat kernel $H_t$ of the $k$-tree can be viewed
as
a basic building block for the heat kernel of any $k$-regular graph,
which in turn is closely related to many major invariants of the graph.

\section{The heat kernel of the $k$-tree and the heat kernel of a $k$-regular
graph}

For a $k$-regular graph $G$, 
there is a natural mapping $\pi$ from $T_k$ to
$G$  so that for each vertex $x$ in $T_k$, the
neighbors of $x$ are mapped to neighbors of
$\pi (x)$ in $G$ in an one-to-one fashion.
Let $H_t$ denote the heat kernel of $T_k$. We here abuse
the notation by writing $H_t(x,y) = H_t(0, d(x,y))$ for two 
vertices $x$ and $y$ at distance $d(x,y)$ in $T_k$.

%We note that a similar upper bound was given in \cite{mckay1} as
%asymptotic estimates for $r_{2j}$.
\begin{lemma}
\label{red}
For a $k$-regular graph $G$,
there is a covering $\pi$ from $T_k$ to $G$
and the heat kernel $h_t$ of $G$ satisfies
\[ h_t(u,v) = \Sum_{y \in \pi^{-1}(u)} H_t(0,d(x,y)) \]
where $v= \pi(x)$, $d(x,y)$ denotes the distance between
$x$ and $y$ in $T_k$ and $H_t$ denotes the heat kernel of
$T_k$.
\end{lemma}
In a graph $G$,
a {\it walk} of length $s$ is a sequence of vertices
$(v_0,v_1,\cdots,v_s)$ where $\{v_i,v_{i+1} \}$
is an edge for $i=0,\cdots,s-1$.
If $v_0=v_s$, it is called a closed walk rooted at $v_0$.
A walk 
$(v_0,v_1,\cdots,v_s)$ 
is said to be {\it irreducible } if 
$v_j \not = v_{j+2}$ for $j=0,\cdots,s-2$.
If $v_j=v_{j+2}$ for some $j$, we can reduce
the walk by deleting $v_j $ and $v_{j+1}$. A walk is
said to be totally reducible if it can be reduced to 
a trivial walk of length $0$.
Let $r_j$ denote the number of totally reducible 
walk rooted at any vertex. In McKay \cite{mckay, mckay1}, 
$r_j$'s have been extensively examined. {}From the definition
of the heat kernel, we have the following:

%We note that a similar upper bound was given in \cite{mckay1} as
%asymptotic estimates for $r_{2j}$.
\begin{lemma}
\label{m7}
In a $k$-regular graph, the number $r_s$ of totally reducible 
walks of length $s$ rooted at any vertex satisfies
\[ H_t(0,0) = e^{-t} \Sum_{j \geq 0} r_j \frac { (t/k)^j}{j!}
\]
where $H_t$ is the heat kernel of the infinite tree $T_k$.
\end{lemma}
\proof
We observe that $r_j$ is exactly the number of rooted closed walks of length
$j$ in the infinite tree $T_k$.  {}From the definition of $H_t$ we have
\begin{eqnarray*}
H_t&= &e^{-t} \cdot e^{A/k}\\
&=& e^{-t} (I + A \frac t k + A^2 \frac{(t/k)^2}{2!} + \cdots )
\end{eqnarray*}
where $A$ denotes the adjacency operator. 
Lemma \ref{m7} then follows.
\qed

\begin{lemma}
\label{red1}
For odd $j$, $r_j$ is zero and for the even case, we have
\begin{eqnarray*}
r_{2j}
% &=& \frac{\partial^{2j}}{\partial t^{2j}} e^t H_t(0,0) \\
&=& 
\frac{4^{j+1} k (k-1)^{j+1}}{\pi} \Int_0^{\pi/2} \frac{\sin^2 x \cos^{2j}x}
{k^2-4(k-1) \cos^2x} dx\\
&\leq& \frac{4^j k (k-1)^{j+1} }{2 j \sqrt{ \pi j} (k-2)^2}.
\end{eqnarray*}
\end{lemma}
\proof
The proof follows from Lemma \ref{red} and Lemma \ref{m7}  which imply:
\begin{eqnarray*}
r_{2j} &=& \frac{\partial^{2j}}{\partial t^{2j}} ( e^t H_t(0,0))
\\
&=& 
\frac{4^{j+1} k (k-1)^{j+1}}{\pi} \Int_0^{\pi/2} \frac{\sin^2 x \cos^{2j}x}
{k^2-4(k-1) \cos^2x} dx.
%\\
%&\leq& \frac{4^j k (k-1)^{j+1}}{j \sqrt{\pi j} (k-2)^2}
\end{eqnarray*}
Therefore we have
\begin{eqnarray*}
r_{2j} 
&\leq& 
\frac{4^{j+1} k (k-1)^{j+1}}{\pi (k-2)^2} \Int_0^{\pi/2} 
{\sin^2 x \cos^{2j}x} dx \\
&=& 
\frac{4^{j+1} k (k-1)^{j+1}}{\pi (k-2)^2(2j+1)} \Int_0^{\pi/2} 
{ \cos^{2j+2}x} dx \\
&=& 
\frac{4^{j+1} k (k-1)^{j+1}}{\pi (k-2)^2(2j+1)}
\frac{2j+1}{2j+2} \frac{2j-1}{2j} \ldots \frac 1 2 \frac {\pi} 4\\
&\leq&
\frac{4^{j+1} k (k-1)^{j+1}}{\pi (k-2)^2}
\frac {\sqrt{\pi}} {8 (j+1) \sqrt{ j} } 
\\
&=&
\frac{4^{j} k (k-1)^{j+1} }
 {2(j+1) \sqrt{\pi j} (k-2)^2} .
\end{eqnarray*}
\qed

We note that a similar upper bound was given in \cite{mckay1} as
an asymptotic estimate for $r_{2j}$.

\begin{lemma}
\label{ma6}
For a $k$-regular graph $G$,
there is a covering $\pi$ from $T_k$ to $G$ and
the heat kernel $h_t(u,v)$ of $G$ satisfies
\[ h_t(u,v) = \Sum_{a=0}^{\infty} c_a H_t(0,a) \]
where $c_a$ denotes the number of irreducible 
walks from $v$ to $u$ of length $a$. 
\end{lemma}

%We consider a homogeneous graph $\Gamma$
%with an associated group $\mathcal H$ and an edge-generating set $\mathcal K$.
%In other words, $\Gamma$ is vertex-transitive under the action of $\mathcal H$
%and we can identify $V$ with the coset space $\mathcal H/\mathcal I$ where
%${\mathcal I} = \{ g \in {\mathcal H} : gv = v \}$ ,
%for a fixed vertex $v$, 
%denotes the {\it isotropy} group.
%A vertex $v$ in $\Gamma$ is adjacent to $gv$ for $g $ in $\mathcal K$.
%Here we require the generating set $\mathcal K$ to be symmetric, i.e., 
%$g \in K$ if and only if $g^{-1} \in {\mathcal  K}$.

%\begin{cor}
%For a homogenous graph $\Gamma$ with an associated group $H$, an
%edge-generating set $\mathcal K$ and an isotropy group $\mathcal I$,
%there is a covering $\pi$ from $T_k$ to $\Gamma$ and
%the heat kernel $h_t(u,v)$ of $G$ satisfies
%\[ h_t(u,v) = \Sum_{a=0}^{\infty} c_a H_t(0,a) \]
%where $c_a$ denotes the number of
%products $g_1g_2 \ldots g_a \in {\mathcal I}$ such that 
%$g_i \not = g_{i+1}^{-1}$.
%\end{cor}

%The proof follows immediately from Lemma \ref{ma6}.

%In a $k$-regular graph $G$, let $A_j$ be a matrix with rows and columns indexed by
%the vertices of $G$ and $A_j(u,v)$ denotes the number
%of irreducible walks of length $j$ joining $u$ and
%$v$. Clearly, $A_1$ is just the adjacency matrix $A$
%and $A_j$ satisfies
%the following recurrence:
%\[  A_j = A A_{j-1} - (k-1) A_{j-2} \]
%for $j \geq 3$, $A_0=I$, $ A_1=A$ and $A_2 = A^2 - k I$.
%It is easy to show that $A_j$ is a polynomial in $A$.
%In fact, we have
%\[ A_j=(k-1)^{j/2}  P_j(\frac{A}{2 \sqrt {k-1}}) -
%(k-1)^{(j-2)/2}  P_{j-2}(\frac{A}{2 \sqrt {k-1}}) \]
%for $j \geq 2$
% where $P_j$ is the Chebyshev polynomial of the second kind satisfying
%$P_j(x)=\sin((j+1)\theta)/\sin \theta$ with $x = \cos \theta$. 
%Clearly, $A_1 = \sqrt{k-1} P_1( \frac{A}{2 \sqrt {k-1}})$.
%We note that the generating function $F(y)=\Sum_{j \geq 0} P_j(x) y^j$ satisfies
%\[ F(y) =\Sum_{j \geq 0} P_j(x) y^j =
%\frac{1-y^2/(k-1)}{1-2xy+y^2}. \]
%Suppose the eigenvalues of the Laplacian $\mathcal L$ of $G$ are of the form $1-
%\frac{2 \sqrt{k-1}}{k} \cos \theta_j$ with the associated orthonormal
%eigenfunction $\phi_j$ (Here $\theta_j$ could be a complex number). 
%Then the $(u,v)$-entry of $A_j$ can be expressed as
%\[ (k-1)^{s/2} \Sum_j \frac{\sin(s+1)\theta_j-(k-1)^{-1}\sin(s-1)\theta_j}
%{\sin \theta_j} \phi_j(u) \phi_j(v) \]
%for $s \geq 1$.
%This is exactly the number of irreducible walks of length $s$ between $u$ and
%$v$ in $G$.
%In particular, for a vertex transitive graph $G$, the irreducible walks of 
%length $s$ from $v$ to itself is
%\begin{eqnarray*}
% c_s& =& \frac{(k-1)^{s/2}}{|V(G)|}\Sum_v \Sum_j \frac{\sin(s+1) \theta_j
%-(k-1)^{-1}\sin(s-1)\theta_j}{\sin
%\theta_j} \phi_j(v)^2 \\
% & =& \frac{(k-1)^{s/2}}{|V(G)|} \Sum_j \frac{\sin(s+1) \theta_j
%-(k-1)^{-1}\sin(s-1)\theta_j}{\sin
%\theta_j}
%\end{eqnarray*}
%\begin{lemma}
%For a $k$-regular vertex-transitive graph $G$, 
%the heat kernel $h_t(v,v)$ of $G$ satisfies
%\[ h_t(v,v) =\Sum_{a=0}^{\infty} c_a H_t(0,a) \]
%where $c_0=1$ and for $s \geq 1$,
%\[ c_s = \frac{(k-1)^{s/2}}{|V(G)|} \Sum_j \frac{\sin(s+1) \theta_j
%-\frac{1}{k-1} \sin (s-1)\theta_j}{\sin
%\theta_j}. \]
%\end{lemma}
\section{Spanning trees in a $k$-regular graph}
For a connected graph $G$, we consider
the $\zeta$-function
\begin{eqnarray*}
\zeta(s) = \Sum_{i \not =0} \frac{1}{\lambda_i^s}
\end{eqnarray*}
where $\lambda_i$ ranges over all nonzero eigenvalues of $G$.

It can be easily checked that
\[- \zeta'(0)=  \sum_{i \not = 0} \log  \lambda_i = \log \prod_{i \not = 0} \lambda_i \]
where $\log$ denotes the natural logarithm.
\begin{theorem}
For a connected graph $G$, the number 
$\tau(G)$ of spanning trees in $G$ is
equal to
\[ \frac{\prod_x d_x}{\sum_x d_x} e^{- \zeta'(0)} \]
where $d_x$ denotes the degree of $x$.
\end{theorem}
\proof
Suppose we consider the characteristic polynomial
$p(x) $ of the Laplacian $\mathcal L$.
\[ p(x) = det ( {\mathcal L} - x I) . \]
The coefficient of the linear term is exactly
\[ - \prod_{i \not = 0} \lambda_i. \]
On the other hand,
\[ p(x) = det T^{-1} det ( L -x T) = (\prod_x d_x )^{-1}p_1(x). \]
By the well known matrix-tree theorem,
the coefficient of the linear term of $p_1(x)$ is
exactly $- \sum_x d_x $ times the number of spanning trees of
$G$.
\qed

Thus, the number of spanning trees of 
a $k$-regular graph on $n$ vertices satisfies
\begin{equation}
\label{eq2}
 \tau(G) ~=~ \frac{ k^{n-1}}{n} e^{-\zeta'(0)}.
\end{equation}
In the rest of the paper, we assume that $G$ is $k$-regular.

The trace function ${\mathit Tr}~h_t$ of $G$ satisfies
\begin{eqnarray*}
{\mathit Tr} ~h_t &=& \sum_i e^{-t \lambda_i}. 
\end{eqnarray*}
Therefore the zeta function satisfies
\begin{equation}
\label{eq3}
 \zeta(s) = \frac{1}{\Gamma(s)} \Int_0^{\infty} t^{s-1} ({\mathit Tr}~h_t -1) 
dt 
\end{equation}
by using the fact that
\begin{equation}
\frac 1 {\Gamma(z)}  
\Int_0^{\infty} e^{-\rho t} t ^{z-1} dt = \frac{1}{\rho^z}. 
\end{equation}
\section{The maximum number of spanning trees in $k$-regular graphs}
McKay \cite{mckay1} gave the following bounds for
the maximum number of spanning trees over all  $k$-regular 
graphs $G_n$
on $n$ vertices:
\[ c_1  \frac{ 1 }{n}  C^n 
\leq 
 {\rm max} ~ \tau(G) \leq c_2  \frac{ \log n }{n}  C^n 
\]
where
\[ C = \frac{(k-1)^{k-1}}{(k^2-2k)^{k/2-1}} \]
and $c_1$ and $c_2$  depend only on $k$ ( in some complicated formula).
He conjectured that the upper bound is the right order for $\max \tau(G_n)$.
Here we will simplify the upper bound and prove that indeed
it is best possible within a constant factor.
\begin{theorem}
\label{t3}
For $k \geq 3$, the number $\tau(G_n)$ of spanning trees in a $k$-regular graph
$G_n$ 
on $n$ vertices satisfies
\[  \tau(G_n)  \leq 
 (1+o(1))   \frac{ 2 \log n }{k n \log k } 
\left(\frac{(k-1)^{k-1}}{( k^2-2k)^{k/2-1}}\right)^n
.
\]
\end{theorem}
\begin{theorem}
\label{t4}
For $k \geq 8$, there are $k$-regular graphs $G$ on $n$ vertices  having
the  number $\tau(G_n)$ of spanning trees 
satisfying
\[  \tau(G)  \geq 
 (1+o(1))    \frac{  \log n }{k n \log k} \left(\frac{(k-1)^{k-1}}
{( k^2-2k)^{k/2-1}}\right)^n.
\]
\end{theorem}

We first need to establish the relation between
the heat kernels $h_t$ and $H_t$.
Let $r'_j$ denote
the total number of rooted closed walks of length $j$ which are not totally
reducible. We then have
\begin{eqnarray*}
 {\mathit Tr}~h_t 
 & =& e^{-t} \sum_{j \geq 0} (n r_j+r'_j) \frac{(t/k)^j}{j!} \\
  & =& n H_t(0,0) + e^{-t} \sum_{j \geq 0} r'_j \frac{(t/k)^j}{j!}.
\end{eqnarray*}
{}From equation (\ref{eq3}), we have
\[ \zeta(s) =: \zeta_0(s)+\zeta_1(s) \]
where
\begin{eqnarray*}
 \zeta_0(s)& =&  \frac{n}{\Gamma(s)} \Int_0^{\infty} t^{s-1} H_t(0,0) dt 
\end{eqnarray*}
and
\begin{eqnarray*}
\zeta_1(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 0} r'_j \frac{(t/k)^j}{j!} - e^t \right).
\end{eqnarray*}

We have
\begin{eqnarray*}
 \zeta_0(s)& =&  \frac{n}{\Gamma(s)} \Int_0^{\infty} t^{s-1} H_t(0,0) dt 
\\
&=& \frac{2n k(k-1)} {\pi \Gamma(s)} \Int_0^{\infty} t^{s-1} 
\Int_0^{\pi} \frac{e^{-t(1-\frac{2 \sqrt{k-1}}{k} \cos x )} \sin^2 x}
{k^2-4(k-1) \cos^2 x} dx dt 
\\
&=& \frac{2n k(k-1)} {\pi }  
\Int_0^{\pi}\frac {1}{(1-\frac{2 \sqrt{k-1}}{k} \cos x)^s} \cdot
 \frac{ \sin^2 x}
{k^2-4(k-1) \cos^2 x} dx . 
\end{eqnarray*}
Therefore
\begin{eqnarray}
\label{z0}
 \zeta_0'(0)& =&  
-\frac{2n k(k-1)} {\pi }  
\Int_0^{\pi}
 \frac{ \sin^2 x}
{k^2-4(k-1) \cos^2 x}   
\log (1-\frac{2 \sqrt{k-1}}{k} \cos x)
d x
\nonumber \\
&=&
n \log  \frac {k^{k/2} (k-2)^{k/2-1}} {(k-1)^{k-1}}.
\end{eqnarray}
The above integral is evaluated by using the following formula
given in  \cite{mckay1}:
\[ \frac{k}{2 \pi}  \Int_{-\omega}^{\omega} 
\frac {(\omega^2-x^2)^{1/2}}{k^2-x^2} \log (1-\gamma x) dx =
- \log \left(\eta (\frac{k-\eta}{k-1})^{k/2-1} \right)
\]
where $| \gamma | = 1/k < 1/\omega$, $\omega = 2\sqrt{k-1}$ and
 $\eta 
= \frac{1-(1-4(k-1)\gamma^2)^{1/2}}{2(k-1) \gamma^2}$.

It remains to evaluate $\zeta'_1(0)$. 
We note that 
\begin{eqnarray*}
n r_j + r'_j &=& {\mathit Tr} {A}^j \\
&=& k^j \Sum_i (1-\lambda_i)^j.
\end{eqnarray*}
So, we have, for odd j,
\begin{eqnarray*}
\frac{r'_{j}}{k^{j}} \geq 1 + \Sum_{i \not = 0} (1-\lambda_i)^j.
\end{eqnarray*}
For the even case,
\begin{eqnarray}
\frac{r'_{2j}}{k^{2j}} \geq 1 + \Sum_{i \not = 0} (1-\lambda_i)^{2j} -
\frac{n 4^j k (k-1)^{j+1}}{j \sqrt{\pi j}(k-2)^2}. 
\end{eqnarray}
%We consider
%\[ \beta = \lceil \frac{ \log n}{\log \frac {k^2}{4(k-1)}} \rceil \]
For a fixed value $\beta$ (which will be chosen later),
we have
\begin{eqnarray*}
\zeta_1(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 0} r'_j \frac{(t/k)^j}{j!} - e^t \right) dt
\\
&\geq&
  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( -\Sum_{j = 0}^{2 \beta -1}  \frac{(t/k)^j}{j!}  \right) dt
\\
&&+
  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j > 2\beta }( r'_j \frac{(t/k)^j}{j!} - 
  \frac{(t/k)^j}{j!})  \right) dt.
\end{eqnarray*}
We note 
that for $j \geq 1$, and
 \[ \rho(s) = 
  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1} e^{-t} (\frac{t^j}{j!})dt 
\]
we have
\begin{equation}
\label{prime}
\rho'(0) = \frac 1 j. 
\end{equation}

Therefore 
\begin{eqnarray}
\label{z1}
 \zeta_1'(0)
&\geq& -\Sum_{j=1}^{2 \beta -1} \frac 1 j + \zeta'_2(0) 
\nonumber
\\
&\geq& - \log (2 \beta) + \zeta'_2(0)
\end{eqnarray}
where
we define
\begin{eqnarray*}
\zeta_2(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq  2\beta} ( r'_j \frac{(t/k)^j}{j!} -
  \frac{(t/k)^j}{j!})  \right).
\end{eqnarray*}
Here, we have
\begin{eqnarray*}
\zeta_2(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 2\beta} 
\frac{t^j}{j!} \left(
 \Sum_{i \not = 0} (1-\lambda_i)^{j} -
\Sum_{j \geq \beta}
\frac{n 4^j k (k-1)^{j+1}}{j \sqrt{\pi j}(k-2)^2k^{2j}} 
\right)
    \right).
\end{eqnarray*}
By using equation (\ref{prime}) and inequality (\ref{z1}), we have
\begin{eqnarray}
\label{z2}
\zeta'_2(0) &\geq&
 \Sum_{j \geq 2 \beta} 
 \Sum_{i \not = 0} (1-\lambda_i)^{j} \frac 1 j -
\Sum_{j \geq  \beta}
\frac{n 4^j k (k-1)^{j+1}}{j^2 \sqrt{\pi j} (k-2)^2 k^{2j}} 
\nonumber\\
&\geq&
-\Sum_{j \geq  \beta}
\frac{n 4^j k (k-1)^{j+1}}{j^2 \sqrt{\pi j}(k-2)^2 k^{2j}} 
\nonumber \\
&\geq&
-2 \frac{n 4^{\beta} k (k-1)^{\beta+1}}{\beta^2 \sqrt{\pi \beta}(k-2)^2 k^{2
\beta}} 
\end{eqnarray}
by using $\lambda_i \leq 2$
and the fact that $\sum_{j \geq 2 \beta} (1-\lambda_i)^j /j \geq 0$ .

Now, we are ready to prove Theorem \ref{t3} and \ref{t4}.

\noindent
{\it Proof of Theorem \ref{t3}: }

{}From (\ref{eq2}) and (\ref{z0}), we have 
\begin{eqnarray}
\label{eq7}
\tau(G) & =& \frac{k^{n-1}}{n} e^{-\zeta'_0(0)-\zeta'_1(0)} \nonumber\\
& = &\frac{k^{n-1}}{n} \left(\frac{(k-1)^{k-1}}{k^{k/2} (k-2)^{k/2-1}}\right)^n
e^{-\zeta'_1(0)} \nonumber\\
& = &\frac{1}{kn} \left(\frac{(k-1)^{k-1}}{ (k^2-2k)^{k/2-1}}\right)^n
e^{-\zeta'_1(0)}.
\end{eqnarray}
By using the preceding lower bounds of $\zeta'_1$ in (\ref{z1}), we have
\begin{eqnarray*}
\tau(G)
& \leq &\frac{2\beta}{kn} \left(\frac{(k-1)^{k-1}}{( k^2-2k)^{k/2-1}}\right)^n
e^{-\zeta'_2(0)}.
\end{eqnarray*}
We now choose $\beta$ as:
\[ \beta = \lceil \frac{ \log n}{\log \frac {k^2}{4(k-1)}} \rceil. \]
{}From (\ref{z2}), we have
\begin{eqnarray*}
\zeta'_2(0) &\geq&
-2 \frac{n 4^{\beta} k (k-1)^{\beta+1}}{\beta^2 \sqrt{\pi \beta}(k-2)^2 k^{2
\beta}} 
\\
&\geq&
-2 \frac{ k (k-1)}
{\beta^2 \sqrt{\pi \beta}(k-2)^2 }. 
\end{eqnarray*}
Therefore, we have
\begin{eqnarray*}
\tau(G) 
& \leq &\frac{2\beta}{kn} \left(\frac{(k-1)^{k-1}}{ (k^2-2k)^{k/2-1}}\right)^n
e^{-\zeta'_2(0)}
\\
&\leq&
 (1+o(1) )  \frac{ 2 \log n }{k n \log k } \left(
\frac{(k-1)^{k-1}}{( k^2-2k)^{k/2-1}}\right)^n.
\end{eqnarray*}
Theorem \ref{t3} is proved.
\qed


\noindent
{\it Proof of Theorem \ref{t4}: }

%From (\ref{eq7}), it suffices to establish upper bounds for
%$\zeta'_1(0)$.

For a graph with girth (the length of the smallest cycle) $ g$, we can take
$\beta = \lfloor g/2 \rfloor $ and we have
\begin{eqnarray*}
\zeta_1(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 0} r'_j \frac{(t/k)^j}{j!} - e^t \right) dt
\\
&=&
  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( -\Sum_{j = 0}^{g}  \frac{(t/k)^j}{j!}  \right) dt
\\
&& + ~~
  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j > { g} }( r'_j \frac{(t/k)^j}{j!} - 
  \frac{(t/k)^j}{j!})  \right) dt.
\end{eqnarray*}
\begin{eqnarray}
\label{eq8}
 \zeta_1'(0)
&\leq& -\Sum_{j=1}^{ g-1} \frac 1 j + \zeta'_2(0) 
\nonumber
\\
&\leq& - \log { g} + \zeta'_2(0)
\end{eqnarray}
where
here we will need to use some known results on random $k$-regular graphs.
 Erd\H{o}s and Sachs \cite{ES63} proved that
 with positive probability, say at least   $  1/2$, 
there is a $k$-regular graph 
on $n$ vertices having  girth $g$ satisfying 
\[  g = (1+o(1)) \frac {\log n}{\log k} \]
as $n$ approaches infinity.
Friedman \cite{fried} showed that
with probability approaches $1$, the expected number of irreducible walks $c_j(v)$ rooted at a vertex
$v$ of length $j$, for $k \geq 8$, is
\begin{eqnarray*}
E( c_j(v)) &=&
 k (k-1)^{j-1} ( \frac 1 n + Err_{n,j})
\end{eqnarray*}
where
\[ Err_{n,j} = 
O \left((ckj)^c (\frac{j^{2 \sqrt k}}{n^{1+ \sqrt{k-1}/2}} + \frac 
1 {k^{j/2}})\right). 
\]
We note that in the original paper of Friedman, only the case
for even $k$ was treated. However, the argument of counting
irreducible ``words" made of   letters can be extended to counting
walks on the $k$-trees for odd $k$ in a similar way.

The expected number  of  closed walks of length $j$  satisfies (see \cite{fried})
\[
k^j \left(1+ (n-1)p_{j,0} +
\sum_{s=1}^j n p_{j,s} Err_{n,s}
\right)
\]
where $p_{j,s}$ is the probability that a random walk of length $j$ reduces
to an irreducible walk of size $s$.
Hence, the number $r'_j$ of not totally
reducible walks of length $j$ satisfies
\[
E(\frac{r'_j}{k^j}) = 1-p_{j,0} +
\sum_{s=1}^j n p_{j,s} Err_{n,s}.
\]
Since $p_{j,s} \leq 2^j k^{-j+s}$, we have
\begin{eqnarray*}
\zeta_2(s) &=&  \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 2 \beta } 
 ( r'_j \frac{(t/k)^j}{j!} -
  \frac{(t/k)^j}{j!})  \right)
\\
&\leq&
 \frac 1 {\Gamma(s)} \Int_0^{\infty} t^{s-1}
e^{-t} \left( \Sum_{j \geq 2 { \beta}} 
  \frac{(t/k)^j}{j!}
2^j \sum_{s=0}^j k^{-j+s}
  (cks)^c (\frac{s^{2 \sqrt k} 2^s}{n^{\sqrt{k-1}/2}} + 
\frac 1 {(k-1)^{s/2}}) 
\right).
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
\zeta'_2(0) 
&\leq&
 \Sum_{j \geq { g}} 
  \frac 1 j
\sum_{s=1}^j
2^j k^{-j+s}
 (cks)^c (\frac{s^{2 \sqrt k} 2^s}{n^{\sqrt{k-1}/2}} + \frac 1 {(k-1)^{s/2}}) 
\\
&=& o(1).
\end{eqnarray*}
Using (\ref{eq7}) and combining the preceding bounds , we have 
\begin{eqnarray*}
\tau(G) & =& 
\frac{1}{kn} \left(\frac{(k-1)^{k-1}}{( k^2-2k)^{k/2-1}}\right)^n
e^{-\zeta'_1(0)}
\\
&\geq& 
\frac{g}{kn} \left(\frac{(k-1)^{k-1}}{( k^2-2k)^{k/2-1}}\right)^n
e^{-\zeta'_2(0)}
\\
&\geq&
(1+o(1))  \frac{ \log n }{kn \log k} \left(\frac{(k-1)^{k-1}}
{( k^2-2k)^{k/2-1}}\right)^n.
\end{eqnarray*}
This completes the proof of Theorem \ref{t4}.
\qed


\begin{thebibliography}{99}
\bibitem{benson}
C. T. Benson,
Minimal regular graphs of girth eight and twelve,
{\it Canad. J. Math.} {\bf 18} (1996), 1091-1094.

\bibitem{biggs} N. Biggs,
Algebraic Graph Theory, Cambridge University Press, 1993.

\bibitem{br} R. Brooks,  
The spectral geometry of $k-$regular graphs, Journal D'analyse
Math\'{e}matrique, 57 (1991) 120-151.

\bibitem{chy} J. Cheeger and S.-T. Yau,
A lower bound for the heat kernel,
{\it Communications on Pure and Applied Mathematics}
XXXIV (1981), 465-480.

\bibitem{cds} D. M. Cvetkovi\'c, M. Doob and H. Sachs,
{\it Spectra of graphs}, Academic Press, New York, 1980.

\bibitem{cy1} F. R. K. Chung and S.-T. Yau,
A combinatorial trace formula,
{\it Tsing Hua Lectures on Geometry and Analysis},
(ed. S.-T. Yau), International Press, Cambridge,
Massachusetts, 1997, 107-116.

\bibitem{ch0} F. R. K. Chung,
{\it Spectral Graph Theory},
CBMS Lecture Notes, 1997 , AMS Publication.
\bibitem{ES63} P. Erd\H{o}s and H. Sachs,
Regul\"{a}re Graphen gegenebener Teillenweite mit Minimaler Knotenzahl,
Wiss. Z. Univ. Halle -- Wittenberg, {\it Math. Nat. R.} {\bf 12}
(1963), 251-258.

\bibitem{fh}
W. Feit and G. Higman,
The non-existence of certain generalized polygons, 
{\it J. Algebra} {\bf 1} (1964), 114-131.
\bibitem{fried}
J. Friedman,
On the second eigenvalues and random walks in random $d$-regular
graphs,
{\it Combinatorica} {\bf 11} (1991), 331-362.
\bibitem{kel} A. K. Kelmans,
On properties of the characteristic polynomial of
a graph, {\it Kibernetiku-Na Sluzbu Kommunizmu}
{\bf 4} Gosenergoizdat, Moscow, 1967.

\bibitem{gm}
C. D. Godsil and B. D. McKay,
Feasibility conditions for the existence of walk-regular graphs,
{\it Linear Algebra Appl.}, {\bf 30} (1980), 51-61.
\bibitem{k} F. Kirchhoff,
\"{U}ber die Aufl\"{o}sung der Gleichungen, auf welche
man bei der Untersuchung der linearen Verteilung galvanischer
Str\"{o}me gef\"{u}hrt wird, {\it Ann. Phys. chem.}
72 (1847) 497-508.
\bibitem{mck9}
B. D. McKay,
Backtrack programming and the graph isomorphism problem,
M. Sc. Thesis, University of Melbourne, 1976.
\bibitem{mckay}
B. D. McKay,
The expected eigenvalue distribution of a large regular graph,
{\it Linear Algebra and its Applications} {\bf 40} (1981),
203-216.
\bibitem{mckay1}
B. D. McKay,
Spanning trees in regular graphs,
{\it Europ. J. Combinatorics} {\bf 4} (1983), 149-160.
\bibitem{sarnak}
Peter Sarnak,
{\it Some Applications of Modular Forms},
Cambridge University Press, New York, 1990.

\bibitem{ys} Richard M. Schoen and S.-T. Yau, {\em Lectures on Differential
Geometry}, International Press, Cambridge, Massachusetts, 1994.
\bibitem{sing}
R. R. Singleton,
On minimal graphs of maximum even girth,
{\it J. Comb. Th} {\bf 1} (1966), 306-322.

\end{thebibliography}

\end{document}