Coverings, Heat Kernels and Spanning Trees

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)) 2log n kn log k ( (k-1)ᵏ⁻¹ (k²-2k)k/2-1)ⁿ spanning trees, which is best possible within a constant factor.