Coverings, heat kernels and spanning trees

Fan Chung ^{†} ^{∗}

University of Pennsylvania Philadelphia, Pennsylvania 19104 chung@hans.math.upenn.edu

S.-T. Yau ^{†}

Harvard University Cambridge, Massachusetts 02138 yau@math.harvard.edu

Submitted: May 1, 1998; Accepted: December 12, 1998. AMS Subject Classification: 05C50, 05Exx, 35P05, 58G99.

Abstract

We consider a graph G and a covering 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} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n}

spanning trees, which is best possible within a constant factor.

1 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 × V → ℝ satisfying

w(u, v) = w(v, u) and w(u, v) ≥ 0.

∗Research supported in part by NSF Grant No. DMS 98-01446 †Research supported in part by NSF Grant No. DMS 95-04834

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} = ∑_{u} w(u, 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.

2 The coverings of graphs

Suppose we have two graphs G̃ and G. We say G̃ is a covering of G (or G is covered by G̃) if there is a mapping π : V (G̃) → V (G) satisfying the following two properties:

(i) There is an m ∈ ℝ^{+} ∪ {∞}, called the index of π, such that for u, v ∈ V (G), we have

∑_{\begin{matrix}x∈π^{−1}(u) \\ y∈π^{−1}(v) \end{matrix}} w(x, y) = m w(u, v).

(ii) For x, y ∈ V (G̃) with π(x) = π(y) and v ∈ V (G), we have

∑_{z∈π^{−1}(v)} w(z, x) = ∑_{z′∈π^{−1}(v)} w(z′, y).

Remark 1: For simple graphs G and G̃, (i) is equivalent to (i’) For every {u, v} ∈ E(G), we have

|{{x, y} ∈ E(G̃) : π(x) = u, π(y) = v}| = m.

And (ii) is equivalent to (ii’) For x, y ∈ V (G̃) with π(x) = π(y), and v adjacent to π(x) in G, we have

|N(x) ∩ π^{−1}(v)| = |N(y) ∩ π^{−1}(v)|.

In other words, π^{−1} defines a so-called equitable partition of V (G̃) which has been studied extensively in the literature. The reader is referred to Cvetković, Doob and Sachs [5], McKay [14], Godsil and McKay [12].

Example 1: Suppose 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}.

Example 2: A graph G̃ is said to be a regular covering of G if for a fixed vertex v in V (G) and for any vertex x of V (G̃), G̃ is a covering of G under a mapping π_{x} which maps x into v. In addition, if π_{x}^{−1} is just x, we say G̃ is a strong regular covering of G. A graph G is said to be 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 π_{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 [2].

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 G̃ of G, the vertices v in G can have preimages π^{−1}(v) of different sizes (as in Example 2). In addition, the degrees of vertices in 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:

Fact 1 Suppose G̃ is a covering of G under π with index m. Then for x ∈ π^{−1}(v), we have

|π^{−1}(v)| ∑_{z∈π^{−1}(u)} w(z, x) = mw(u, v).

The proof follows from (i) and (ii). For a simple graph, Fact 1 implies

|π^{−1}(v)| · |N(x) ∩ π^{−1}(u)| = m.

As an immediate consequence, we have

Fact 2 Suppose G̃ is a covering of G under π with edge multiplicity m. Then for x, y ∈ π^{−1}(v), we have

d_{x} = d_{y}.

3 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) = \{ \begin{matrix}d_{v} − w(v, v) & if u = v, \\ −w(u, v) & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

In particular, for a function f : V → ℝ, we have

Lf(v) = ∑_{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) Laplacian of G is defined to be

L(u, v) = \{ \begin{matrix}1 − \frac{w(v, v)}{d_{v}} & if u = v, and d_{v} ≠ 0, \\ −\frac{w(u, v)}{\sqrt{d_{u}d_{v}}} & if u and v are adjacent, \\ 0 & otherwise. \end{matrix}

In other words, we have

L = T^{−1/2}LT^{−1/2}.

For a k-regular graph, we have

L = I − \frac{1}{k}A

where A is the adjacency matrix.

We denote the eigenvalues of L by 0 = λ_{0} ≤ λ_{1} ⋯ ≤ λ_{n−1} (which are sometimes called the eigenvalues of G). If G is connected, we have 0 < λ_{1}. The reader is referred to [7] for various properties of eigenvalues of a graph.

In this paper, we mainly deal with connected graphs. Let g denote an eigenfunction of L associated with eigenvalue λ. It is sometimes convenient to consider f = T^{−1/2}g, called the harmonic eigenfunction, which satisfies, for every vertex v of G,

∑_{u}(f(v) − f(u))w(u, v) = λd_{v}f(v).

For a graph G, we consider the heat kernel h_{t}, which is defined for t ≥ 0 as follows:

h_{t} = ∑_{i} e^{−λ_{i}t}P_{i}
= e^{−tL}
= I − tL + \frac{t^{2}}{2} L^{2} − …  (1)

where P_{i} denotes the projection into the eigenspace associated with eigenvalue λ_{i}. In particular,

h_{0} = I.

and h_{t} satisfies the heat equation

\frac{∂h_{t}}{∂t} = −Lh_{t}.

For any two vertices x, y ∈ V, we have

h_{t}(x, y) = ∑_{i} e^{−λ_{i}t}ϕ_{i}(x)ϕ_{i}(y)

where ϕ_{i}’s are orthonormal eigenfunctions of the Laplacian L.

In particular, the trace of h_{t} satisfies

T rh_{t} = ∑_{x} h_{t}(x, x)
= ∑_{i} e^{−λ_{i}t}.

4 Eigenvalues of a graph and its covering

If 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 [12] (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 G̃ is a covering of G, we can “lift” the harmonic eigenfunction f of G to G̃ by defining, for each vertex x in G̃, f(x) = f(u) where u = π(x). From definition (ii) of covering, we have

∑_{y}(f(x) − f(y))w(x, y) = ∑_{v}(f(u) − f(v))w(u, v)
= λd_{x}.

Therefore we have Lemma 1 If G̃ is a covering of G, then an eigenvalue of G is an eigenvalue of G̃.

For each x ∈ π^{−1}(v),

∑_{y}(f(x) − f(y))w(x, y) = λf(x)d_{x}.

By summing over x in π^{−1}(v), we have

∑_{x∈π^{−1}(v)} ∑_{y}(f(x) − f(y))w(x, y) = λ ∑_{x∈π^{−1}(v)} f(x)d_{x}.

We define the induced mapping of f in G, denoted by πf : V (G) → ℝ by

(πf)(v) = ∑_{x∈π^{−1}(v)} \frac{f(x)d_{x}}{d_{v}} .

Then, for g = πf, we have

∑_{u}(g(v) − g(u))w(u, v) = λg(v)d_{v}.

If g is nontrivial, λ is an eigenvalues of G̃. Thus we have shown the following:

Lemma 2 Suppose G̃ is a covering of G and. If a harmonic eigenfunction f of G̃, associated with an eigenvalue λ, has a nontrivial image in G, then λ is also an eigenvalue for G.

Lemma 3 Suppose G̃ is a strong regular covering of G. Then, G̃ and G have the same eigenvalues.

Proof: For any nontrivial harmonic eigenfunction f of 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 2, we see that any eigenvalue of G̃ is an eigenvalue of G. By Lemma 1, we conclude that G̃ and G have the same eigenvalues. □

Therefore the eigenvalues of a covering graph G̃ can be determined by computing the eigenvalues of a smaller graph G. However, the multiplicities for the eigenvalues in G̃ are, in general, different from those in G since, for example, G̃ and G can have different numbers of vertices. Nevertheless, the multiplicities of eigenvalues of G̃ and G are related through the relations of their heat kernels.

Lemma 4 Suppose G̃ is a covering of G. Let h̃_{t} and h_{t} denote the heat kernels of G̃ and G, respectively. Then we have

∑_{x∈π^{−1}(u)} ∑_{y∈π^{−1}(v)} h̃_{t}(x, y) = \sqrt{|π^{−1}(u)| · |π^{−1}(v)|}h_{t}(u, v).

Proof: We note that the heat kernel h_{t}(u, v) satisfies

h_{t}(u, v) = e^{−t} ∑_{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}, …, 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, …, r − 1.) We want to show that the total weights of the paths in 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{|π^{−1}(u_{0})| · |π^{−1}(u_{r})|}. Let p_{r−1} denote the walk u_{0}, …, u_{r−1}. Suppose u_{r−1} ≠ u_{r} (The other case is easy). For each path p̃_{r−1} lifted from p_{r−1}, its extensions to paths lifted from p_{r} has total weights

w(p̃_{r−1}) · ∑_{z∈π^{−1}(u_{r})} \frac{−w(u_{r−1}, z)}{\sqrt{d(u_{r−1})d(z)}}

= w(p̃_{r−1})\frac{−mw(u_{r−1}, u_{r})/|π^{−1}(u_{r−1})|}{\sqrt{md(u_{r−1})md(u_{r})/(|π^{−1}(u_{r−1})| |π^{−1}(u_{r})|)}}

= w(p̃_{r−1})\frac{−w(u_{r−1}, u_{r})}{\sqrt{d(u_{r−1})d(u_{r})}}\sqrt{\frac{|π^{−1}(u_{r})|}{|π^{−1}(u_{r−1})|}}.

By summing over all p̃_{r−1}, we have

∑_{x∈π^{−1}(u)} ∑_{y∈π^{−1}(v)} S_{r}(x, y) = \sqrt{|π^{−1}(u)| · |π^{−1}(v)|}S_{r}(u, v).

Therefore, we complete the proof of Lemma 4. □

As a consequence of Lemma 4, we have

Corollary 1 Suppose G̃ is a strong regular covering of G. Let h̃_{t} and h_{t} denote the heat kernels of G̃ and G, respectively. For x ∈ π^{−1}(u), we have

∑_{y∈π^{−1}(v)} h̃_{t}(x, y) = \sqrt{\frac{|π^{−1}(v)|}{|π^{−1}(u)|}}h_{t}(u, v).

Corollary 2 Suppose G is a distance regular graph which is a covering of a path P with vertices v_{0}, …, v_{p} where p = D(G). Suppose G and P have heat kernels h̃_{t} and h_{t}, respectively. For any two vertices x and y in G with distance d(x, y) = r, we have

h̃_{t}(x, y) = \sqrt{|π^{−1}(u_{r})|}h_{t}(v_{0}, v_{r}).

Theorem 1 Suppose G̃ is a strong regular covering of G. Let v denote the vertex of G with preimage in G̃ consisting of one vertex. Then any eigenvalue λ of G̃ has multiplicity

n ∑_{i} \frac{ϕ_{i}^{2}(v)}{∥ϕ_{i}∥^{2}},

where n = |V (G̃)| and ϕ_{i} ’s span the eigenspace of λ in G. If the eigenvalue λ has multiplicity 1 in G with eigenfunction ϕ, then the multiplicity of λ in G̃ is

\frac{nϕ^{2}(v)}{∥ϕ∥^{2}}.

Proof: Suppose G̃ has heat kernel H_{t} and G has heat kernel h_{t}. Since G̃ is a strong regular covering of G, we have

T r(h̃_{t}) = ∑_{x∈V (G̃)} H_{t}(x, x)
= nh_{t}(v, v)
= n ∑_{j} e^{−tλ_{j}} \frac{ϕ_{j}^{2}(v)}{∥ϕ_{j}∥^{2}} .

Therefore, the multiplicity of λ_{j} in G̃ is exactly

\frac{n ϕ_{j}^{2}(v)}{∥ϕ_{j}∥^{2}}

if the multiplicity of λ in G is 1 and . In general, the multiplicity of λ in G̃ is

n ∑_{i} \frac{ϕ_{i}^{2}(v)}{∥ϕ_{i}∥^{2}}

where ϕ_{i} ’s span the eigenspace of λ in G. □

As an immediate consequence of Theorem 1, we have the following:

Corollary 3 A distance regular graph G with diameter D has D + 1 distinct eigenvalues λ’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 λ in G is

\frac{nϕ^{2}(x)}{∥ϕ∥^{2}}

where n is the number of vertices in G and ϕ is the eigenfunction of λ of the Laplacian of P.

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 ϕ_{0} = (\sqrt{3}, \sqrt{6}, \sqrt{18}), ϕ_{1} = (\sqrt{3}, 1, −\sqrt{2}) and ϕ_{2} = (\sqrt{6}, −2\sqrt{2}, 1), respectively. Using Lemma 8, we see that eigenvalues 0, 2/3, 5/3 have multiplicities 1, 5, 4 in G, respectively.

5 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 kregular 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 [1, 3, 9, 17, 19]. Here we will give a self-contained proof for establishing the explicit formula for the kernel of the k-tree, for k ≥ 3. For the case of k = 2, T_{2} is just the infinite path. This special case and its cartesian products were examined in [6].

T_{k} can be regarded as a covering of the following weighted path P. The vertex of P is {0, 1, 2, … }. For j > 0, the edge joining j − 1 to j has weight k(k − 1)^{j−1}. the covering mapping π is defined by assigning all vertices in the j-th level to vertex j in P. The Laplacian L for the weighted path has entries

L(i, j) = \{ \begin{matrix}1 & if i = j, \\ −\frac{1}{\sqrt{k}} & if (i, j) = (0, 1) or (1, 0), \\ −\frac{\sqrt{k−1}}{k} & if |i − j| = 1, i, j ≠ 0, \\ 0 & otherwise. \end{matrix}

We observe that L 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 ≥ 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{πj}{l} for j = 1, …, 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 × l matrix L^{(l)}, for l ≥ 3:

L^{(l)} = ( \begin{matrix}1 & −\frac{1}{\sqrt{k}} & 0 & ⋯ & ⋯ & 0 \\ −\frac{1}{\sqrt{k}} & 1 & −\frac{\sqrt{k−1}}{k} & 0 & ⋯ & 0 \\ 0 & −\frac{\sqrt{k−1}}{k} & 1 & −\frac{\sqrt{k−1}}{k} & ⋯ & 0 \\ ⋯ & ⋯ & ⋯ & ⋯ & −\frac{\sqrt{k−1}}{k} & 0 \\ 0 & ⋯ & ⋯ & ⋯ & 1 & −\sqrt{\frac{k−1}{k}} \\ 0 & ⋯ & ⋯ & ⋯ & −\sqrt{\frac{k−1}{k}} & 1 \end{matrix} )

where

L^{(l)}(i, j) = \{ \begin{matrix}1 & if i = j, \\ −\frac{1}{\sqrt{k}} & if (i, j) = (0, 1) or (1, 0), \\ −\frac{\sqrt{k−1}}{k} & if |i − j| = 1, 0 < i, j < l, \\ −\sqrt{\frac{k−1}{k}} & if (i, j) = (l − 1, l) or (l, l − 1), \\ 0 & otherwise. \end{matrix}

The eigenvalues of L^{(l)} are 0, 2 and

1 − \frac{2\sqrt{k − 1}}{k} cos \frac{πj}{l} for j = 1, …, l − 1.

The eigenfunction ϕ_{0} associated with eigenvalue 0 is ϕ_{0} = f_{0}/∥f_{0}∥ where f_{0} is defined as follows:

f_{0}(0) = 1,
f_{0}(p) = \sqrt{k(k − 1)^{p−1}},  for 1 ≤ p ≤ l − 1,
f_{0}(l) = \sqrt{(k − 1)^{l−1}}.

The eigenfunction ϕ_{l} associated with eigenvalue 2 is ϕ_{l} = f_{l}/∥f_{l}∥ where f_{l} is defined as follows:

f_{l}(0) = 1,
f_{l}(p) = (−1)^{p}\sqrt{k(k − 1)^{p−1}},  for 1 ≤ p ≤ l − 1,
f_{l}(l) = (−1)^{l}\sqrt{(k − 1)^{l−1}}.

The eigenfunction ϕ_{j}, for j = 1, ⋯, l−1, associated with eigenvalue 1−\frac{2\sqrt{k−1}}{k} cos \frac{πj}{l} is f_{j}/∥f_{j}∥ where

f_{j}(0) = \sqrt{\frac{k}{k − 1}} sin \frac{πj}{l} ,
f_{j}(p) = sin \frac{πj(p + 1)}{l} − \frac{1}{k − 1} sin \frac{πj(p − 1)}{l},  for 1 ≤ p ≤ l − 1,
f_{j}(l) = −\frac{\sqrt{k}}{k − 1} sin \frac{πj}{l} .

It is easy to compute, for j = 1, ⋯, l − 1,

∥f_{j}∥^{2} = \frac{lk^{2}}{2(k − 1)^{2}} (1 − \frac{4(k − 1)}{k^{2}} cos^{2} \frac{πj}{l}).

Therefore the heat kernel h^{(l)} of P^{(l)} satisfies

h^{(l)}(0, 0) = ∑_{j=1}^{l−1} \frac{e^{−t(1− \frac{2\sqrt{k−1}}{k} cos \frac{πj}{l})} sin^{2} \frac{πj}{l}}{\frac{lk}{2(k−1)}(1 − \frac{4(k−1)}{k^{2}} cos^{2} \frac{πj}{l})} + \frac{1}{∥f_{0}∥^{2}} + \frac{1}{∥f_{l}∥^{2}} .

When l approaches infinity, the heat kernel h of P satisfies:

h_{t}(0, 0) = \frac{2k(k − 1)}{π} ∫_{0}^{π} \frac{e^{−t(1− \frac{2\sqrt{k−1}}{k} cos x)} sin^{2} x}{k^{2} − 4(k − 1) cos^{2} x}dx.

In general, for a ≥ 1, we have

h_{t}(0, a) = \frac{2\sqrt{k(k − 1)}}{π} ∫_{0}^{π} \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.

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 4 and the fact that the infinite k-tree is a covering of P, we have the following:

Theorem 2 The heat kernel H_{t} of the infinite k-tree satisfies

H_{t}(0, 0) = \frac{2k(k − 1)}{π} ∫_{0}^{π} \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}{π(k − 1)^{a/2−1}} ∫_{0}^{π} \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.

Corollary 4 The heat kernel H_{t}(0, 0) of the infinite k-tree can be written as

H_{t}(0, 0) = e^{−t} ∑_{r≥0} ∑_{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} ∑_{s≥0}(\frac{4(k − 1)}{k^{2}})^{2s} \frac{(2s − 1)!!}{(2s + 2)!!} ∑_{0≤j≤s} \frac{t^{2}j}{(2j)!}

where m!! denotes the product of all numbers less than or equal to m and having the same parity as m.

We note that the first sum in the corollary above appeared in [15]. 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.

6 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 π from T_{k} to G so that for each vertex x in T_{k}, the neighbors of x are mapped to neighbors of π(x) in G in an oneto-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}.

Lemma 5 For a k-regular graph G, there is a covering π from T_{k} to G and the heat kernel h_{t} of G satisfies

h_{t}(u, v) = ∑_{y∈π^{−1}(u)} H_{t}(0, d(x, y))

where v = π(x), d(x, y) denotes the distance between x and y in T_{k} and H_{t} denotes the heat kernel of T_{k}.

In a graph G, a walk of length s is a sequence of vertices (v_{0}, v_{1}, ⋯, v_{s}) where {v_{i}, v_{i+1}} is an edge for i = 0, ⋯, s − 1. If v_{0} = v_{s}, it is called a closed walk rooted at v_{0}. A walk (v_{0}, v_{1}, ⋯, v_{s}) is said to be irreducible if v_{j} ≠ v_{j+2} for j = 0, ⋯, 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 [15, 16], r_{j}’s have been extensively examined. From the definition of the heat kernel, we have the following:

Lemma 6 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} ∑_{j≥0} r_{j} \frac{(t/k)^{j}}{j!}

where H_{t} is the heat kernel of the infinite tree T_{k}.

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

H_{t} = e^{−t} · e^{A/k}
= e^{−t}(I + A\frac{t}{k} + A^{2} \frac{(t/k)^{2}}{2!} + ⋯)

where A denotes the adjacency operator. Lemma 6 then follows. □

Lemma 7 For odd j, r_{j} is zero and for the even case, we have

r_{2j} = \frac{4^{j+1}k(k − 1)^{j+1}}{π} ∫_{0}^{π/2} \frac{sin^{2} x cos^{2j} x}{k^{2} − 4(k − 1) cos^{2} x}dx
≤ \frac{4^{j}k(k − 1)^{j+1}}{2j\sqrt{πj}(k − 2)^{2}} .

Proof: The proof follows from Lemma 5 and Lemma 6 which imply:

r_{2j} = \frac{∂^{2j}}{∂t^{2j}} (e^{t}H_{t}(0, 0))
= \frac{4^{j+1}k(k − 1)^{j+1}}{π} ∫_{0}^{π/2} \frac{sin^{2} x cos^{2j} x}{k^{2} − 4(k − 1) cos^{2} x}dx.

Therefore we have

r_{2j} ≤ \frac{4^{j+1}k(k − 1)^{j+1}}{π(k − 2)^{2}} ∫_{0}^{π/2} sin^{2} x cos^{2j} xdx
= \frac{4^{j+1}k(k − 1)^{j+1}}{π(k − 2)^{2}(2j + 1)} ∫_{0}^{π/2} cos^{2j+2} xdx
= \frac{4^{j+1}k(k − 1)^{j+1}}{π(k − 2)^{2}(2j + 1)} \frac{2j + 1}{2j + 2} \frac{2j − 1}{2j} … \frac{1}{2} \frac{π}{4}
≤ \frac{4^{j+1}k(k − 1)^{j+1}}{π(k − 2)^{2}} \frac{\sqrt{π}}{8(j + 1)\sqrt{j}}
= \frac{4^{j}k(k − 1)^{j+1}}{2(j + 1)\sqrt{πj}(k − 2)^{2}} .
□

We note that a similar upper bound was given in [16] as an asymptotic estimate for r_{2j}.

Lemma 8 For a k-regular graph G, there is a covering π from T_{k} to G and the heat kernel h_{t}(u, v) of G satisfies

h_{t}(u, v) = ∑_{a=0}^{∞} c_{a}H_{t}(0, a)

where c_{a} denotes the number of irreducible walks from v to u of length a.

7 Spanning trees in a k-regular graph

For a connected graph G, we consider the ζ-function

ζ(s) = ∑_{i≠0} \frac{1}{λ_{i}^{s}}

where λ_{i} ranges over all nonzero eigenvalues of G.

It can be easily checked that

−ζ′(0) = ∑_{i≠0} log λ_{i} = log ∏_{i≠0} λ_{i}

where log denotes the natural logarithm.

Theorem 3 For a connected graph G, the number τ(G) of spanning trees in G is equal to

\frac{∏_{x} d_{x}}{∑_{x} d_{x}} e^{−ζ′(0)}

where d_{x} denotes the degree of x.

Proof: Suppose we consider the characteristic polynomial p(x) of the Laplacian L.

p(x) = det(L − xI).

The coefficient of the linear term is exactly

− ∏_{i≠0} λ_{i}.

On the other hand,

p(x) = detT^{−1}det(L − xT) = (∏_{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 − ∑_{x} d_{x} times the number of spanning trees of G. □

Thus, the number of spanning trees of a k-regular graph on n vertices satisfies

τ(G) = \frac{k^{n−1}}{n} e^{−ζ′(0)}.  (2)

In the rest of the paper, we assume that G is k-regular.

The trace function T r h_{t} of G satisfies

T r h_{t} = ∑_{i} e^{−tλ_{i}}.

Therefore the zeta function satisfies

ζ(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}(T r h_{t} − 1)dt  (3)

by using the fact that

\frac{1}{Γ(z)} ∫_{0}^{∞} e^{−ρt}t^{z−1}dt = \frac{1}{ρ^{z}} .  (4)

8 The maximum number of spanning trees in kregular graphs

McKay [16] 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} ≤ max τ(G) ≤ 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 τ(G_{n}). Here we will simplify the upper bound and prove that indeed it is best possible within a constant factor.

Theorem 4 For k ≥ 3, the number τ(G_{n}) of spanning trees in a k-regular graph G_{n} on n vertices satisfies

τ(G_{n}) ≤ (1 + o(1))\frac{2 log n}{kn log k} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} .

Theorem 5 For k ≥ 8, there are k-regular graphs G on n vertices having the number τ(G_{n}) of spanning trees satisfying

τ(G) ≥ (1 + o(1))\frac{log n}{kn log k} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} .

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

T r h_{t} = e^{−t} ∑_{j≥0}(nr_{j} + r′_{j})\frac{(t/k)^{j}}{j!}

= nH_{t}(0, 0) + e^{−t} ∑_{j≥0} r′_{j} \frac{(t/k)^{j}}{j!} .

From equation (3), we have

ζ(s) =: ζ_{0}(s) + ζ_{1}(s)

where

ζ_{0}(s) = \frac{n}{Γ(s)} ∫_{0}^{∞} t^{s−1}H_{t}(0, 0)dt

the electronic journal of combinatorics 6 (1999), #R12 16 and

ζ_{1}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥0} r′_{j} \frac{(t/k)^{j}}{j!} − e^{t}) .

We have

ζ_{0}(s) = \frac{n}{Γ(s)} ∫_{0}^{∞} t^{s−1}H_{t}(0, 0)dt
= \frac{2nk(k − 1)}{πΓ(s)} ∫_{0}^{∞} t^{s−1} ∫_{0}^{π} \frac{e^{−t(1− \frac{2\sqrt{k−1}}{k} cos x)} sin^{2} x}{k^{2} − 4(k − 1) cos^{2} x}dxdt
= \frac{2nk(k − 1)}{π} ∫_{0}^{π} \frac{1}{(1 − \frac{2\sqrt{k−1}}{k} cos x)^{s}} · \frac{sin^{2} x}{k^{2} − 4(k − 1) cos^{2} x}dx.

Therefore

ζ′_{0}(0) = −\frac{2nk(k − 1)}{π} ∫_{0}^{π} \frac{sin^{2} x}{k^{2} − 4(k − 1) cos^{2} x} log(1 − \frac{2\sqrt{k − 1}}{k} cos x)dx
= n log \frac{k^{k/2}(k − 2)^{k/2−1}}{(k − 1)^{k−1}} .  (5)

The above integral is evaluated by using the following formula given in [16]:

\frac{k}{2π} ∫_{−ω}^{ω} \frac{(ω^{2} − x^{2})^{1/2}}{k^{2} − x^{2}} log(1 − γx)dx = − log (η(\frac{k − η}{k − 1})^{k/2−1})

where |γ| = 1/k < 1/ω, ω = 2\sqrt{k − 1} and η = \frac{1−(1−4(k−1)γ^{2})^{1/2}}{2(k−1)γ^{2}} .

It remains to evaluate ζ′_{1}(0). We note that

nr_{j} + r′_{j} = T rA^{j}
= k^{j} ∑_{i}(1 − λ_{i})^{j}.

So, we have, for odd j,

\frac{r′_{j}}{k^{j}} ≥ 1 + ∑_{i≠0}(1 − λ_{i})^{j}.

For the even case,

\frac{r′_{2j}}{k^{2j}} ≥ 1 + ∑_{i≠0}(1 − λ_{i})^{2j} − \frac{n4^{j}k(k − 1)^{j+1}}{j\sqrt{πj}(k − 2)^{2}} .  (6)

the electronic journal of combinatorics 6 (1999), #R12 17 For a fixed value β (which will be chosen later), we have

ζ_{1}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥0} r′_{j} \frac{(t/k)^{j}}{j!} − e^{t}) dt
≥ \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (− ∑_{j=0}^{2β−1} \frac{(t/k)^{j}}{j!} ) dt

+\frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j>2β}(r′_{j} \frac{(t/k)^{j}}{j!} − \frac{(t/k)^{j}}{j!} )) dt.

We note that for j ≥ 1, and

ρ(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t}(\frac{t^{j}}{j!})dt

we have

ρ′(0) = \frac{1}{j}.  (7)

Therefore

ζ′_{1}(0) ≥ − ∑_{j=1}^{2β−1} \frac{1}{j} + ζ′_{2}(0)
≥ − log(2β) + ζ′_{2}(0)  (8)

where we define

ζ_{2}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥2β}(r′_{j} \frac{(t/k)^{j}}{j!} − \frac{(t/k)^{j}}{j!} )) .

Here, we have

ζ_{2}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥2β} \frac{t^{j}}{j!} (∑_{i≠0}(1 − λ_{i})^{j} − ∑_{j≥β} \frac{n4^{j}k(k − 1)^{j+1}}{j\sqrt{πj}(k − 2)^{2}k^{2j}} )) .

By using equation (7) and inequality (8), we have

ζ′_{2}(0) ≥ ∑_{j≥2β} ∑_{i≠0}(1 − λ_{i})^{j} \frac{1}{j} − ∑_{j≥β} \frac{n4^{j}k(k − 1)^{j+1}}{j^{2}\sqrt{πj}(k − 2)^{2}k^{2j}}
≥ − ∑_{j≥β} \frac{n4^{j}k(k − 1)^{j+1}}{j^{2}\sqrt{πj}(k − 2)^{2}k^{2j}}
≥ −2\frac{n4^{β}k(k − 1)^{β+1}}{β^{2}\sqrt{πβ}(k − 2)^{2}k^{2β}}  (9)

by using λ_{i} ≤ 2 and the fact that ∑_{j≥2β}(1 − λ_{i})^{j}/j ≥ 0 .

Now, we are ready to prove Theorem 4 and 5. Proof of Theorem 4:

From (2) and (5), we have

τ(G) = \frac{k^{n−1}}{n} e^{−ζ′_{0}(0)−ζ′_{1}(0)}
= \frac{k^{n−1}}{n} (\frac{(k − 1)^{k−1}}{k^{k/2}(k − 2)^{k/2−1}} )^{n} e^{−ζ′_{1}(0)}
= \frac{1}{kn} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} e^{−ζ′_{1}(0)}.  (10)

By using the preceding lower bounds of ζ′_{1} in (8), we have

τ(G) ≤ \frac{2β}{kn} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} e^{−ζ′_{2}(0)}.

We now choose β as:

β = ⌈\frac{log n}{log \frac{k^{2}}{4(k−1)}} ⌉.

From (9), we have

ζ′_{2}(0) ≥ −2\frac{n4^{β}k(k − 1)^{β+1}}{β^{2}\sqrt{πβ}(k − 2)^{2}k^{2β}}
≥ −2\frac{k(k − 1)}{β^{2}\sqrt{πβ}(k − 2)^{2}} .

Therefore, we have

τ(G) ≤ \frac{2β}{kn} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} e^{−ζ′_{2}(0)}
≤ (1 + o(1))\frac{2 log n}{kn log k} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} .

Theorem 4 is proved. □ Proof of Theorem 5:

For a graph with girth (the length of the smallest cycle) g, we can take β = ⌊g/2⌋ and we have

ζ_{1}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥0} r′_{j} \frac{(t/k)^{j}}{j!} − e^{t}) dt

= \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (− ∑_{j=0}^{g} \frac{(t/k)^{j}}{j!} ) dt

+ \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j>g}(r′_{j} \frac{(t/k)^{j}}{j!} − \frac{(t/k)^{j}}{j!} )) dt.

ζ′_{1}(0) ≤ − ∑_{j=1}^{g−1} \frac{1}{j} + ζ′_{2}(0)
≤ − log g + ζ′_{2}(0)  (11)

where here we will need to use some known results on random k-regular graphs. Erdős and Sachs [8] 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 [10] 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 ≥ 8, is

E(c_{j}(v)) = k(k − 1)^{j−1}(\frac{1}{n} + Err_{n,j})

where

Err_{n,j} = O ((ckj)^{c}(\frac{j^{2\sqrt{k}}}{n^{1+\sqrt{k−1}/2}} + \frac{1}{k^{j/2}} )) .

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 [10])

k^{j} (1 + (n − 1)p_{j,0} + ∑_{s=1}^{j} np_{j,s}Err_{n,s})

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} + ∑_{s=1}^{j} np_{j,s}Err_{n,s}.

Since p_{j,s} ≤ 2^{j}k^{−j+s}, we have

ζ_{2}(s) = \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥2β}(r′_{j} \frac{(t/k)^{j}}{j!} − \frac{(t/k)^{j}}{j!} ))

≤ \frac{1}{Γ(s)} ∫_{0}^{∞} t^{s−1}e^{−t} (∑_{j≥2β} \frac{(t/k)^{j}}{j!} 2^{j} ∑_{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}} )) .

Therefore,

ζ′_{2}(0) ≤ ∑_{j≥g} \frac{1}{j} ∑_{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).

Using (10) and combining the preceding bounds , we have

τ(G) = \frac{1}{kn} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} e^{−ζ′_{1}(0)}
≥ \frac{g}{kn} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} e^{−ζ′_{2}(0)}
≥ (1 + o(1))\frac{log n}{kn log k} (\frac{(k − 1)^{k−1}}{(k^{2} − 2k)^{k/2−1}} )^{n} .

This completes the proof of Theorem 5. □

References

[1] C. T. Benson, Minimal regular graphs of girth eight and twelve, Canad. J. Math. 18 (1996), 1091-1094.

[2] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1993.

[3] R. Brooks, The spectral geometry of k−regular graphs, Journal D’analyse Mathématrique, 57 (1991) 120-151.

[4] J. Cheeger and S.-T. Yau, A lower bound for the heat kernel, Communications on Pure and Applied Mathematics XXXIV (1981), 465-480.

[5] D. M. Cvetković, M. Doob and H. Sachs, Spectra of graphs, Academic Press, New York, 1980.

[6] F. R. K. Chung and S.-T. Yau, A combinatorial trace formula, Tsing Hua Lectures on Geometry and Analysis, (ed. S.-T. Yau), International Press, Cambridge, Massachusetts, 1997, 107-116.

[7] F. R. K. Chung, Spectral Graph Theory, CBMS Lecture Notes, 1997 , AMS Publication.

[8] P. Erdős and H. Sachs, Reguläre Graphen gegenebener Teillenweite mit Minimaler Knotenzahl, Wiss. Z. Univ. Halle – Wittenberg, Math. Nat. R. 12 (1963), 251-258.

[9] W. Feit and G. Higman, The non-existence of certain generalized polygons, J. Algebra 1 (1964), 114-131.

[10] J. Friedman, On the second eigenvalues and random walks in random d-regular graphs, Combinatorica 11 (1991), 331-362.

[11] A. K. Kelmans, On properties of the characteristic polynomial of a graph, Kibernetiku-Na Sluzbu Kommunizmu 4 Gosenergoizdat, Moscow, 1967.

[12] C. D. Godsil and B. D. McKay, Feasibility conditions for the existence of walkregular graphs, Linear Algebra Appl., 30 (1980), 51-61.

[13] F. Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. chem. 72 (1847) 497-508.

[14] B. D. McKay, Backtrack programming and the graph isomorphism problem, M. Sc. Thesis, University of Melbourne, 1976.

[15] B. D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra and its Applications 40 (1981), 203-216.

[16] B. D. McKay, Spanning trees in regular graphs, Europ. J. Combinatorics 4 (1983), 149-160.

[17] Peter Sarnak, Some Applications of Modular Forms, Cambridge University Press, New York, 1990.

[18] Richard M. Schoen and S.-T. Yau, Lectures on Differential Geometry, International Press, Cambridge, Massachusetts, 1994.

[19] R. R. Singleton, On minimal graphs of maximum even girth, J. Comb. Th 1 (1966), 306-322.