# Constructing heat kernels on infinite graphs 111Keywords: heat kernels,
graphs, parametrix. 2020 MSC: 35R02, 35K08, 05C05, 39A12.

Jay Jorgenson 222The first-named author acknowledges grant support from PSC-
CUNY Award 65400-00-53, which was jointly funded by the Professional Staff
Congress and The City University of New York. Anders Karlsson 333The second-
named author acknowledges grant support by the Swiss NSF grants 200020-200400,
200021-212864 and the Swedish Research Council grant 104651320. Lejla
Smajlović

###### Abstract

Let $G$ be an infinite, edge- and vertex-weighted graph with certain
reasonable restrictions. We construct the heat kernel of the associated
Laplacian using an adaptation of the parametrix approach due to
Minakshisundaram-Pleijel in the setting of Riemannian geometry. This is partly
motivated by the wish to relate the heat kernels of a graph and a subgraph, or
of a domain and a discretization of it. As an application, assuming that the
graph is locally finite, we express the heat kernel $H_{G}(x,y;t)$ as a Taylor
series with the lead term being $a(x,y)t^{r}$, where $r$ is the combinatorial
distance between $x$ and $y$ and $a(x,y)$ depends (explicitly) upon edge and
vertex weights. In the case $G$ is the regular $(q+1)$-tree with $q\geq 1$,
our construction reproves different explicit formulas due to Chung-Yau and to
Chinta-Jorgenson-Karlsson. Assuming uniform boundedness of the combinatorial
vertex degree, we show that a dilated Gaussian depending on any distance
metric on $G$, which is uniformly bounded from below can be taken as a
parametrix in our construction. Our work extends in part the recent articles
[LNY21, CJKS23] in that the graphs are infinite and weighted.

##  1 Introduction

In the seminal article [MP49], Minakshisundaram and Pleijel established a
general method by which one can construct explicitly the heat kernel for the
Laplacian operator associated to a smooth compact Riemannian manifold. As
stated in [MP49], their method is a generalization of previous work by
Carleman. In effect, one begins with an initial approximation for the heat
kernel for time approaching zero, called a parametrix $H$, and then one forms
a Neumann series $F(H)$ of convolutions only involving the parametrix $H$. It
is then shown that $H+F(H)$ equals the heat kernel sought. So, in essence, the
heat kernel is realized as a type of fixed point theorem since one has some
flexibility when choosing the parametrix $H$.

In this paper we will develop a similar methodology by which one can construct
the heat kernel associated to the graph Laplacian for a rather general
infinite graph $X$. Our approach is most directly inspired by [Mi49] and
[Mi53] as well as [Ro83] and [Ch84]. The results of this paper extend results
from [CJKS23] in which a parametrix construction is carried out for finite
graphs whose vertex weight function is identically equal to one, compare also
with [LNY21, section 5]. Moreover, our results complements those from [Wo09]
where the heat kernel on infinite graphs is constructed by exhausting the
infinite graph with finite, connected subgraphs.

One motivation for undertaking this study is the following. Some of the most
significant applications of heat kernel analysis (see [JoLa01, Gr09] and
references therein) come from relating the heat kernels on two spaces $X$ and
$Y$ via a quotient structure $Y\twoheadrightarrow X$, such as Poisson
summation, Jacobi theta inversion and other trace formulas. The parametrix
construction can naturally be used to instead set up a comparison in a
subspace situation $X\hookrightarrow Y$. This is the point of view taken by
Lin, Ngai and Yau in [LNY21], who wrote that it is useful to express the heat
kernel expansions of $X$, a finite graph, in terms of that of $Y$, a complete
graph containing $X$. These authors viewed this in analogy with relating the
heat kernel on a compact $d$-dimensional manifold with $\mathbb{R}^{d}$ as
done in Riemannian geometry. In our setting, since our graphs $X$ are
infinite, this would rather correspond to non-compact manifolds or open
domains in $\mathbb{R}^{d}$. Note that we also allow our space $Y$, via the
parametrix chosen, to be more general, for example it could be a graph
containing $X$ or a domain that $X$ provides a discretization of.

Let $G$ be an infinite connected graph with vertex weights $\theta(x)$ and
edge weights $w_{xy}$ satisfying conditions (G1) and (G2’) given below. The
Laplace operator on functions is

$\Delta_{G}f(x)=\frac{1}{\theta(x)}\sum_{y\in VG}(f(x)-f(y))w_{xy}.$ (1)

See section 2 for all details. The main result of this paper is an explicit
construction of the heat kernel on $G$ associated to this Laplacian, starting
with a parametrix, see Definition 6 for the definition:

######  Theorem 1.

Let $H$ be a parametrix of order $k\geq 0$ for the heat operator
$L_{G}=\Delta_{G}+\partial_{t}$. For $x,y\in VG$ and $t\in\mathbb{R}_{\geq
0}$, let

$F(x,y;t):=\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}H)^{\ast\ell}(x,y;t).$ (2)

This series converges absolutely and uniformly on every compact subset of
$VG\times VG\times\mathbb{R}_{\geq 0}$. The heat kernel $H_{G}$ is given by

$H_{G}(x,y;t)=H(x,y;t)+(H\ast F)(x,y;t)$ (3)

and

$(H\ast F)(x,y;t)=O(t^{k+1})\,\,\,\,\,\text{\rm as $t\rightarrow 0$.}$

Here, $\ast$ denotes the convolution of two functions with a domain $VG\times
VG\times\mathbb{R}_{\geq 0}$, see Definition 3. Our construction allows for a
variety of expressions for the heat kernel, and we focus on two types of
parametrix, the simple Dirac delta function (section 5) and more elaborate
parametrix coming from distance functions (section 6).

First, we show in section 5 that the Dirac delta function
$\frac{1}{\theta(x)}\delta_{x=y}$ on $L^{1}(\theta)$ can be chosen as a
parametrix, under additional assumption that the graph is locally finite,
meaning that for each $x\in VG$, the number of vertices adjacent to $x$ is
finite. Then, in Proposition 9 below we show that by taking the Dirac delta
function as the parametrix in our main theorem, the heat kernel $H_{G}(x,y;t)$
on $G$ can be expressed as

$H_{G}(x,y;t)=\frac{1}{\theta(x)}\delta_{x=y}+\sum_{\ell=1}^{\infty}(-1)^{\ell}\frac{t^{\ell}}{\ell!}\sum_{z_{1},\ldots,z_{\ell-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y),$
(4)

where

$\delta_{x}(y):=\frac{1}{\theta(x)}\left\\{\begin{array}[]{ll}\mu(x),&x=y;\\\
-w_{xy},&x\sim y\\\ 0,&\text{otherwise,}\end{array}\right.\quad x,y\in VG.$
(5)

The combinatorial expression (4) for the heat kernel further highlights the
local nature of the heat diffusion. Specifically, the first $r+1$ terms in the
expansion on the right-hand side of (4) in powers of $t$ depend only on points
that are at combinatorial distance at most $r$ from the starting point $x$.
Moreover, if the combinatorial distance $d(x,y)$ between $x$ and $y$ is $r\geq
2$, then
$\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)=0$
for any choice $z_{1},\ldots,z_{\ell-1}\in VG$ of $\ell-1\leq r-1$ points
which yields the following corollary.

######  Corollary 2.

Let $G$ be an infinite weighted, connected and locally finite graph satisfying
conditions (G1) and (G2’). Then, for all $x,y\in VG$ with the combinatorial
distance $d(x,y)=r\geq 1$ and all $t>0$ we have

$\left|H_{G}(x,y;t)-(-1)^{r}\frac{t^{r}}{r!}c_{r}(x,y)\right|\leq
t^{r+1}C(x,y;t),$

where $c_{r}(x,y)=\sum_{z_{1},\ldots,z_{r-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{r-1}}(y)$
and

$C(x,y;t)=\left|\sum_{\ell=r+1}^{\infty}(-1)^{\ell}\frac{t^{\ell-r-1}}{\ell!}\sum_{z_{1},\ldots,z_{\ell-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)\right|$

is bounded as $t\downarrow 0$.

Therefore, the heat kernel $H_{G}(x,y;t)$, for small time $t$ is
asymptotically equal $\frac{(-1)^{r}}{r!}c_{r}(x,y)t^{r}$. This was proved in
[KLMST16, Theorem 2.2.], with the constant multiplying $t^{r}$ and the upper
bound $C(x,y;t)$ expressed in a different way.

Second, in section 6 we consider a parametrix which is inspired by the
Gaussian as the heat kernel on $\mathbb{R}$ (see [Gr09], section 9 for
generalizations and modifications in higher-dimensional setting). Namely, in
Proposition 12 below we show that, assuming uniform boundedness of
combinatorial vertex degree, for _any_ distance metric $d$ on $G$ such that
$d(x,y)\geq\delta>0$ for all distinct points $x,y\in VG$, the function
$H_{d}:VG\times VG\times[0,\infty)\to[0,\infty)$, defined as

$H_{d}(x,y;t):=\frac{1}{\sqrt{\theta(x)\theta(y)}}\exp(-(\theta(x)\theta(y)d^{2}(x,y))/t)\,\,\,\text{\rm
with}\,\,\,H_{d}(x,y;0)=\lim_{t\downarrow 0}H_{d}(x,y;t)$

can be taken as a parametrix in our construction of the heat kernel.

There has been extensive studies of heat kernels within the field of spectral
graph theory. However, as noted in [LNY21], there are few instances of
explicit evaluations of heat kernels on infinite graphs. The main examples are
lattice graphs (see [CY97, Be03, KN06]) and regular trees (see [CY99] and
[CJK15]). These formulas will be rederived below from the general methodology
we develop in this article (see Example 11). For instance, let $G$ be a
$(q+1)$-regular tree, which has special significance since it is the universal
covering of every $(q+1)$-regular graph, then we have

$H_{G}(x,y;t)=q^{-r/2}e^{-(q+1)t}I_{r}(2\sqrt{q}t)-(q-1)e^{-(q+1)t}\sum_{j=1}^{\infty}q^{-(r+2j)/2}I_{2j+r}(2\sqrt{q}t).$
(6)

where $I_{n}(t)$ is the classical $I$-Bessel function. This is the formula in
[CJK15].

As already mentioned, comparing different heat kernel expressions often leads
to significant consequences. In the graph setting, we can refer to recent
articles [GLY22], [CHJSV23] and [JKS23] that use the heat kernel on the
lattice graph and its quotient to obtain explicit evaluations of trigonometric
sums. See also [HSSS23] for series identities of $I$-Bessel functions, from
which the authors deduce transformation formulas for the Dedekind eta-
function.

By choosing a different metric on $G$, and a few examples are presented in
section 6.1 below, we get different “seeds” $H_{d}$ in the parametrix
construction. Given that in our setting the heat kernel is unique, when
equating the expressions for the heat kernels constructed using $H_{d}$ with
different distances $d$ yields many new identities. Going further, when taking
the Laplace transform of such identities may be particularly useful since the
Laplace transform of a time convolution of two functions equals the product of
Laplace transforms.

When the Laplacian extends to a bounded, self-adjoint operator on
$L^{2}(\theta)$, the heat kernel possesses a spectral expansion in terms of
the eigenvalues and the eigenfunctions of the Laplacian. As such, when using
the parametrix construction of the heat kernel and starting with the seed
$H_{d}$, which is of a geometric nature, one can also deduce identities
relating the sum over the eigenvalues to the length spectrum of the graph.
This, in turn, may serve as a starting point for deducing trace-type formulas,
see for example [CY97], [TW03], [HNT06] or [Mn07]. A similar argument in the
setting of compact hyperbolic Riemann surfaces yields a succinct proof of the
Selberg trace formula; see Remark 3.3 of [GJ18].

###  1.1 Organization of the paper

This paper is organized as follows. We start in section 2 by describing the
assumptions on the graph $G$, followed by section 3 where we define the
convolution on the space $L^{p}(\theta)$ and prove some of its properties,
which ensure that a certain convolution series is convergent. In section 4 we
define the notion of a parametrix and prove our main theorem, Theorem 8, which
computes the heat kernel by starting with a parametrix. We then proceed by
constructing different parametrix and their associated heat kernels. In
section 5 it is proved that the Dirac delta on $L^{1}(\theta)$ can be taken as
the parametrix, under the assumption that the graph $G$ is locally finite. In
section 6 we develop further examples, under assumption that the combinatorial
vertex degree is uniformly bounded on $G$. In particular, we show that the
function $H_{d}$ defined above can be taken as a parametrix for an arbitrary
choice of metric $d$ on $G$ provided $d$ is uniformly bounded from below. We
conclude the paper with several remarks and questions for further studies.

##  2 Our setup

Let $G$ be a countably infinite, vertex-weighted, edge-weighted, and connected
graph with the vertex set $VG$. The vertex weights are defined by the function
$\theta:VG\to(0,\infty)$ with full support, meaning $\theta(x)>0$ for all
$x\in VG$. The edge weights are defined by a nonnegative function $w:VG\times
VG\to[0,\infty)$, and we shall use the notation $w_{xy}=w(x,y)$. We assume
that $w$ is symmetric, meaning that $w_{xy}=w_{yx}$ for all $x,y\in VG$, hence
the graph is undirected. If $w_{xy}=0$ we say there is no edge between the
vertices $x$ and $y$. When $w_{xy}>0$, the vertices $x$ and $y$ are said to be
adjacent or neighbors, and we write $x\sim y$. Furthermore, we assume that
$w_{xx}=0$ for all $x$, meaning that $G$ has no loops. We refer to [Fo13] p.
117 as well as [Fo14] for an interesting probabilistic interpretation of the
edge weights and the vertex weights.

Let $p\in[1,\infty]$ be a real number or $+\infty$, and let $L^{p}(\theta)$
denote the classical $L^{p}$ space of functions on $VG$ with respect to the
pointwise vertex measure $\theta$. Specifically, the function
$f:VG\to\mathbb{C}$ belongs to $L^{p}(\theta)$ for $p\in(1,\infty)$ if and
only if

$\sum_{x\in VG}|f(x)|^{p}\theta(x)<\infty.$

Since $\theta$ has a full support, any $f\in L^{\infty}(\theta)$ is such that
$f$ is uniformly bounded on $VG$. We denote by $\|f\|_{p,\theta}$ the
$L^{p}$-norm of $f$. When $p=2$, the space $L^{2}(\theta)$ is a Hilbert space
with the inner product

$\langle f,g\rangle_{\theta}:=\sum_{x\in VG}f(x)\overline{g(x)}\theta(x).$

Following [KL12], we define the Laplace operator $\Delta_{G}$ acting on
functions $f:VG\rightarrow\mathbb{C}$ by

$\Delta_{G}f(x)=\frac{1}{\theta(x)}\sum_{y\in VG}(f(x)-f(y))w_{xy}.$ (7)

The natural domain of definition is $\mathcal{D}(\Delta_{G}):=\\{f\in
L^{2}(\theta):\,\Delta_{G}f\in L^{2}(\theta)\\}$.

For any $x\in VG$, define

$\mu(x):=\sum_{y:\,x\sim y}w_{xy}.$

For us, we will assume throughout this paper that $\theta$ need not equal
$\mu$. In general, the Laplacian $\Delta_{G}$ is not bounded, nor possesses a
unique self-adjoint extension. For this reason, different authors imposed the
following assumptions on the (infinite) graph $G$.

  * (G1)

Uniform boundedness of the weighted degree. There exists a positive constant
$M$ such that for all $x\in VG$ we have that

$\mu(x):=\sum_{y:\,x\sim y}w_{xy}\leq M.$

  * (G2)

Unbound sum for the vertex weights.

$\sum_{x\in VG}\theta(x)=\infty.$

The assumptions (G1) and (G2) imply that $\Delta_{G}$ with domain
$\mathcal{D}(\Delta_{G})$ is self-adjoint; see [KL12, Theorem 5]. Yet,
$\Delta_{G}$ is not necessarily bounded operator on $L^{2}(\theta)$. The
operator $\Delta_{G}$ is bounded on $L^{2}(\theta)$ if and only if

$A(G,w,\theta):=\sup\limits_{x\in VG}\frac{\mu(x)}{\theta(x)}<\infty,$ (8)

see page 66 of [Da93], [HKLW12] or [KLW21, Theorem 1.27]. In view of this,
throughout this paper we will replace (G2) with the following condition on the
vertex weight function

  * (G2’)

Uniform lower bound for the vertex weights. There exists $\eta>0$ such that

$\inf_{x\in VG}\theta(x)>\eta.$

Condition (G2’) arises naturally in [Fo14]. Conditions (G1) and (G2’) ensure
that $\Delta_{G}$ extends to a bounded operator on $L^{2}(\theta)$ which is,
according to [KL12, Theorem 6], essentially self-adjoint on the set of
compactly supported functions (with the maximal associated Dirichlet form).
Essential self-adjointness means that the operator possesses a unique self-
adjoint extension.

Throghout this paper, the weighted graph $G$ satisfies conditions (G1) and
(G2’).

The _heat kernel_ on the graph $G$ associated to the weighted graph Laplacian
$\Delta_{G,x}$, when acting on functions in the variable $x$, is the unique
solution $H_{G}(x,y;t)$ to the differential equation

$\left(\Delta_{G,x}+\frac{\partial}{\partial t}\right)H_{G}(x,y;t)=0$

with the property that

$\lim_{t\to
0}H_{G}(x,y;t)=\frac{1}{\theta(x)}\delta_{x=y}=\left\\{\begin{array}[]{ll}\frac{1}{\theta(x)},&\text{
if }x=y\\\ 0,&\text{ if }x\neq y\end{array}\right.,$ (9)

where $\delta$ is the Kronecker delta function.

For the proof of the existence and uniqueness of the heat kernel on $G$, we
refer to [Do84], [DM06] for the case when $\theta(x)\equiv 1$ and to [Hu12],
in a general setting. Let us note that the uniqueness essentially follows from
the fact that (G1) and (G2’) imply that $\Delta_{G}$ is stochastically
complete; see [Wo21, Theorem 4.3] as well as the extensive bibliography
therein. Specifically, according to [Wo21, Theorem 3.3], stochastic
completeness is equivalent to unique dependence of the bounded solution to the
heat equation from its initial condition which are given by a bounded function
on $G$.

##  3 Convolution on $L^{p}(\theta)$

For any $p\in[1,\infty]$ we denote by $q$ its conjugate, meaning the number
$q\in[1,\infty]$ such that $\frac{1}{p}+\frac{1}{q}=1$, or $p=1$ if
$q=\infty$. Let us start by defining the convolution of two functions that
belong to conjugate $L^{p}(\theta)$ spaces.

######  Definition 3.

With the notation as above, let $F_{1},F_{2}:VG\times
VG\times\mathbb{R}_{>0}\to\mathbb{R}$ be two functions such that for any
$t>0$, those functions, when viewed as functions on $VG\times VG$, belong to
$L^{p}(\theta)$ in the second variable and $L^{q}(\theta)$ in the first
variable, respectively. Assume further that for all $b>0$ and for all $x,y\in
VG$, the function $\langle
F_{1}(x,\cdot;t-r),F_{2}(\cdot,y;r)\rangle_{\theta}$, which is well defined,
due to the Hölder inequality, is integrable on $[0,b]$. The _convolution_ of
functions $F_{1}$ and $F_{2}$ is defined to be

$\displaystyle(F_{1}\ast F_{2})(x,y;t)$
$\displaystyle:=\int\limits_{0}^{t}\langle
F_{1}(x,\cdot;t-r),F_{2}(\cdot,y;r)\rangle_{\theta}dr$
$\displaystyle=\int\limits_{0}^{t}\sum_{z\in
VG}F_{1}(x,z,t-r)F_{2}(z,y;r)\theta(z)dr.$ (10)

The above convolution is not commutative in general but it is associative,
under suitable assumptions on functions convolved. We have the following
lemma.

######  Lemma 4.

Let $F_{1},F_{2}:VG\times VG\times\mathbb{R}_{>0}\to\mathbb{R}$ be as in
Definition 3. For some $t_{0}>0$, assume there exist constants $C_{1},C_{2}$
and integers $k,\ell\geq 0$ such that for all $0<t<t_{0}$ and all $x,y\in VG$,
we have

$\left\|F_{1}(x,\cdot;t)\right\|_{p,\theta}\leq C_{1}t^{k}\,\,\,\,\,\text{\rm
and}\,\,\,\,\,\left\|F_{2}(\cdot,y;t)\right\|_{q,\theta}\leq C_{2}t^{\ell}.$

Then, for all $x,y\in VG$ we have

$|(F_{1}\ast F_{2})(x,y;t)|\leq
C_{1}C_{2}\frac{k!\ell!}{(k+\ell+1)!}t^{k+\ell+1}\,\,\,\,\,\text{\rm for
$0<t<t_{0}$.}$

###### Proof.

From the Hölder inequality we get

$\displaystyle|(F_{1}\ast F_{2})(x,y;t)|$
$\displaystyle\leq\int\limits_{0}^{t}\left\|F_{1}(x,\cdot;t-r)\right\|_{p,\theta}\left\|F_{2}(\cdot,y;r)\right\|_{q,\theta}dr$
$\displaystyle\leq
C_{1}C_{2}\int_{0}^{t}r^{k}(t-r)^{\ell}\,dr=C_{1}C_{2}\frac{k!\ell!t^{k+\ell+1}}{(k+\ell+1)!},$

as claimed. ∎

Let $f=f(x,y;t):VG\times VG\times\mathbb{R}_{>0}\to\mathbb{R}$ be a function
with the following property. For any $T>0$, for all $t\in(0,T]$, and all
arbitrary, but fixed, $x,y\in VG$ the functions $f(\cdot,y;t):VG\to\mathbb{R}$
and $f(x,\cdot;t):VG\to\mathbb{R}$ belong to $L^{p}(\theta)\cap L^{q}(\theta)$
and the function $f(x,y;\cdot):(0,T]\to\mathbb{R}$ is integrable. For any
positive integer $\ell$ and any such function $f$, we can inductively define
the $\ell$-fold convolution $(f)^{\ast\ell}(x,y;t)$ for $t\in(0,T]$ by setting
$(f)^{\ast 1}(x,y;t)=f(x,y;t)$ and, for $\ell\geq 2$ we put

$(f)^{\ast\ell}(x,y;t):=\left(f\ast(f)^{\ast(\ell-1)}\right)(x,y;t),$

under additional assumption that $(f)^{\ast(\ell-1)}(x,\cdot;t)\in
L^{q}(\theta)$ for all $t\in(0,T]$ and all $\ell\geq 2$.

With this notation we have the following lemma.

######  Lemma 5.

Let $f=f(x,y;t):VG\times VG\times\mathbb{R}_{>0}\to\mathbb{R}$. Assume that
for all $x,y\in VG$ and all $t_{0}\in\mathbb{R}_{>0}$, the function
$f(x,y;\cdot)$ is integrable on the interval $(0,t_{0}]$ and $f(x,\cdot;t)\in
L^{1}(\theta)$ for all $t\in(0,t_{0}]$. Assume further that for all
$t_{0}\in\mathbb{R}_{>0}$ there exists a constant $C$, depending only upon
$t_{0}$, and integer $k\geq 0$ such that

$|f(x,y;t)|\leq Ct^{k}\,\,\,\,\,\text{\rm for all $x,y\in VG$ and
$0<t<t_{0}$.}$

Then the series

$\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast\ell}(x,y;t)$ (11)

converges absolutely and uniformly on every compact subset of $VG\times
VG\times\mathbb{R}_{>0}$. In addition, we have that

$\left(f\ast\left(\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast\ell}\right)\right)(x,y;t)=\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast(\ell+1)}(x,y;t).$
(12)

and

$\sum_{\ell=1}^{\infty}\left|(f)^{\ast\ell}(x,y;t)\right|=O(t^{k})\,\,\,\,\,\text{\rm
as $t\to 0$,}$ (13)

where the implied constant is independent of $x,y\in VG$.

###### Proof.

Let $A$ be an arbitrary compact subset of $VG\times VG\times\mathbb{R}_{>0}$.
Let $t_{0}>0$ be such that $A\subseteq VG\times VG\times(0,t_{0}]$. We apply
Lemma 4, with $p=\infty$, $q=1$ to get that

$\left|(f\ast f)(x,y;t)\right|\leq
C\|f\|_{1,\theta}\frac{t^{k+1}}{(k+1)!},\,\,\,\,\,\text{\rm for all $x,y\in
VG$ and $0<t<t_{0}$.}$ (14)

Similarly, by induction for $\ell\geq 1$ we have the bound that

$\left|(f^{\ast(\ell)})(x,y;t)\right|\leq
C\|f\|_{1,\theta}^{\ell-1}\frac{t^{k+\ell-1}}{(k+\ell-1)!},\,\,\,\,\,\text{\rm
for all $x,y\in VG$ and $0<t<t_{0}$.}$ (15)

The assertion regarding the convergence of (11) now follows from the
Weierstrass criterion and the fact that $A\subseteq VG\times
VG\times(0,t_{0}]$.

Fix $t>0$. The series (11) converges absolutely. When viewed as a function of
$y$, for any arbitrary but fixed $x$ and for any $0<t<t_{0}$, the series
belongs to $L^{\infty}(\theta)$. Therefore,

$\left(f\ast\left(\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast\ell}\right)\right)(x,y;t)=\int\limits_{0}^{t}\sum_{z\in
VG}f(x,z;t-r)\left(\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast\ell}(z,y;r)\right)\theta(z)dr.$
(16)

From the bound (15), combined with the Hölder inequality with $p=1$,
$q=\infty$ we have, for an arbitrary $t\in(0,t_{0})$ and $0<r<t$ that

$\sum_{\ell=1}^{\infty}\sum_{z\in
VG}\left|f(x,z;t-r)(f)^{\ast\ell}(z,y;r)\right|\theta(z)\leq
C\|f\|_{1,\theta}t^{k}\exp(t\|f\|_{1,\theta}).$

Hence we may interchange the sum over $\ell$ with the sum over $z\in VG$ in
(16). Reasoning analogously, one easily shows that we may interchange the
infinite sum over $\ell$ with the integral from $0$ to $t$, to deduce that

$\left(f\ast\left(\sum_{\ell=1}^{\infty}(-1)^{\ell}(f)^{\ast\ell}\right)\right)(x,y;t)=\sum_{\ell=1}^{\infty}(-1)^{\ell}\int\limits_{0}^{t}\sum_{z\in
VG}f(x,z;t-r)(f)^{\ast\ell}(z,y;r)\theta(z)dr,$

which proves (12).

Finally, the bound (15) and the fact that the series (11) converges absolutely
on $VG\times VG\times(0,t_{0}]$ yield that

$\sum_{\ell=1}^{\infty}\left|(f)^{\ast\ell}(x,y;t)\right|\leq
C\|f\|_{1,\theta}t^{k}\exp(t\|f\|_{1,\theta}),$

which proves (13). ∎

##  4 The parametrix construction of the heat kernel on $G$

The heat operator $L_{G}$ on the graph $G$ is defined by

$L_{G}=\Delta_{G}+\frac{\partial}{\partial t}.$ (17)

With this notation, the heat kernel $H_{G}$ on $G$ associated to the Laplacian
$\Delta_{G}$ is the unique solution $H_{G}:VG\times VG\times[0,\infty)$ to the
differential equation

$L_{G,x}H_{G}(x,y;t)=0$

satisfying the initial condition (9). The subscript $x$ on $L_{x}$ indicates
the sum (7) which defines the Laplacian is over neighbors of $x$, the first
space variable.

######  Definition 6.

Let $k\geq 0$ be an integer. A _parametrix_ $H$ order $k$ for the heat
operator $L_{G}$ on $G$ is any continuous function $H=H(x,y;t):VG\times
VG\times[0,\infty)$ which is smooth in time variable $t$, integrable in each
space variable, and satisfies the following properties.

  1. 1.

For all $x,y\in VG$,

$H(x,y;0)=\lim\limits_{t\rightarrow
0}H(x,y;t)=\frac{1}{\theta(x)}\delta_{x=y}.$ (18)

  2. 2.

The function $L_{G,x}H(x,y;t)$ extends to a continuous function on $VG\times
VG\times[0,\infty)$.

  3. 3.

For all $x\in VG$, $t>0$ we have that $\Delta_{G,x}H(x,\cdot;t)$ and
$\frac{\partial}{\partial t}H(x,\cdot;t)$ are in $L^{1}(\theta)$.

  4. 4.

For any $t_{0}>0$ there exists a constant $C=C(t_{0})$, depending only on
$t_{0}$, such that

$|L_{G,x}H(x,y;t)|\leq C(t_{0})t^{k}\,\,\,\,\,\text{\rm for
$t\in(0,t_{0}]$}\,\,\,\text{\rm and all}\,\,\,\text{\rm$x,y\in VG$.}$

Note that the third assumption on the parametrix $H$ implies that
$L_{G,x}H(x,\cdot;t)\in L^{1}(\theta)$.

######  Lemma 7.

Let $H$ be a parametrix for the heat operator on $G$ of any order. Let
$f=f(x,y;t):VG\times VG\times\mathbb{R}_{>0}\to\mathbb{R}$ be a continuous
function in $t$ for all $x,y\in VG$. Assume further that for all $t>0$ the
function $f(x,y;t)$ when viewed as a function on $VG\times VG$ is uniformly
bounded. Then

$L_{G,x}(H\ast f)(x,y;t)=f(x,y;t)+(L_{G,x}H\ast f)(x,y;t)$

for all $x,y\in VG$ and $t\in\mathbb{R}_{>0}$.

###### Proof.

As stated $f(\cdot,y;t)\in L^{\infty}(\theta)$ and
$H(x,\cdot;t),\,\Delta_{G,x}H(x,\cdot;t)\in L^{1}(\theta)$ for all $(x,y;t)\in
VG\times VG\times(0,\infty)$. Therefore, the convolutions $H\ast f$ and
$(\Delta_{G,x}H)\ast f$ are well defined, and we have that

$\displaystyle L_{G,x}(H\ast f)(x,y;t)$
$\displaystyle=\frac{\partial}{\partial t}(H\ast f)(x,y;t)+\Delta_{G,x}(H\ast
f)(x,y;t)$ $\displaystyle=\frac{\partial}{\partial t}(H\ast
f)(x,y;t)+\left((\Delta_{G,x}H)\ast f\right)(x,y;t),$ (19)

where the second equation follows from the fact that the Laplacian acts on the
first variable only.

The function $\sum_{z\in VG}H(x,z;t-r)f(z,y;r)\theta(z)$ is continuous in the
time variable, so we can apply the Leibniz integration formula. Upon doing so,
we obtain that the first term on the right hand side of (19) is equal to

$\displaystyle\frac{\partial}{\partial t}$
$\displaystyle\int\limits_{0}^{t}\sum_{z\in VG}H(x,z;t-r)f(z,y;r)\theta(z)dr$
(20) $\displaystyle=\sum_{z\in
VG}H(x,z;0)f(z,y;t)\theta(z)+\int\limits_{0}^{t}\frac{\partial}{\partial
t}\sum_{z\in VG}H(x,z;t-r)f(z,y;r)\theta(z)dr.$

The assumptions that $f$ is uniformly bounded and that
$\frac{\partial}{\partial t}H(x,\cdot;t)\in L^{1}(\theta)$ combine to yield
that

$\frac{\partial}{\partial t}\sum_{z\in
VG}H(x,z;t-r)f(z,y;r)\theta(z)=\sum_{z\in VG}\frac{\partial}{\partial
t}H(x,z;t-r)f(z,y;r)\theta(z).$

Given that $H(x,z;0)=0$ unless $x=z$, we get from (20) that

$\frac{\partial}{\partial t}\int\limits_{0}^{t}\sum_{z\in
VG}H(x,z;t-r)f(z,y;r)\theta(z)dr=f(x,y;t)+\left(\frac{\partial}{\partial
t}H\ast f\right)(x,y;t).$

Therefore,

$\displaystyle L_{G,x}(H\ast f)(x,y;t)$
$\displaystyle=\frac{\partial}{\partial t}(H\ast f)(x,y;t)+(\Delta_{G,x}H\ast
f)(x,y;t)$ $\displaystyle=f(x,y;t)+\left(\frac{\partial}{\partial t}H\ast
f\right)(x,y;t)+(\Delta_{G,x}H\ast f)(x,y;t)$
$\displaystyle=f(x,y;t)+(L_{G,x}H\ast f)(x,y;t),$

as claimed. ∎

With all this, we now can state the main theorem in this section.

######  Theorem 8.

Let $H$ be a parametrix of order $k\geq 0$ for the heat operator on $G$. For
$x,y\in VG$ and $t\in\mathbb{R}_{\geq 0}$, let

$F(x,y;t):=\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}H)^{\ast\ell}(x,y;t).$
(21)

Then the Neumann series (21) converges absolutely and uniformly on every
compact subset of $VG\times VG\times\mathbb{R}_{\geq 0}$. Furthermore, the
heat kernel $H_{G}$ on $G$ associated to graph Laplacian $\Delta_{G,x}$ is
given by

$H_{G}(x,y;t)=H(x,y;t)+(H\ast F)(x,y;t)$ (22)

and

$(H\ast F)(x,y;t)=O(t^{k+1})\,\,\,\,\,\text{\rm as $t\rightarrow 0$.}$

###### Proof.

Set

$\tilde{H}(x,y;t):=H(x,y;t)+(H\ast F)(x,y;t).$

We want to show that

$L_{G,x}\tilde{H}(x,y;t)=0\,\,\,\,\,\text{\rm and}\,\,\,\,\,\lim_{t\to
0}\tilde{H}(x,y,t)=\frac{1}{\theta(x)}\delta_{x=y}.$ (23)

By Lemma 5, the series $F(x,y;t)$ defined in (21) converges uniformly and
absolutely and has order $O(t^{k})$ as $t\rightarrow 0$. Since $H$ is in
$L^{1}(\theta)$, Lemma 4 then yields the asymptotic bound that

$(H\ast F)(x,y;t)=O(t^{k+1})\,\,\,\,\,\text{\rm as $t\rightarrow 0$.}$

Therefore,

$\lim_{t\to 0}\widetilde{H}(x,y;t)=\lim_{t\to
0}H(x,y;t)=\frac{1}{\theta(x)}\delta_{x=y}.$

It remains to prove the vanishing of $L_{G,x}\tilde{H}$ in (23). For this, we
can apply Lemma 7 to get that

$\displaystyle L_{G,x}\tilde{H}(x,y;t)$
$\displaystyle=L_{G,x}H(x,y;t)+L_{G,x}(H\ast F)(x,y;t)$
$\displaystyle=L_{G,x}H(x,y;t)+\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}{H})^{\ast\ell}(x,y;t)$
$\displaystyle\,\,\,\,\,\,+(L_{G,x}{H})*\left(\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}{H})^{\ast(\ell)}\right)(x,y;t)$
$\displaystyle=L_{G,x}H(x,y;t)+\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}{H})^{\ast\ell}(x,y;t)+\sum_{\ell=1}^{\infty}(-1)^{\ell}(L_{G,x}{H})^{\ast(\ell+1)}(x,y;t)$
$\displaystyle=0,$

To be precise, in the above calculations we used that absolute convergence of
the series defining $F(x,y;t)$ in order to change the order of summation. This
completes the proof. ∎

##  5 Dirac delta as a parametrix

In (22), the function $H(x,y;t)$ is a parametrix, so it is required to satisfy
the reasonably weak conditions given in its definition. In particular, one
does not use any information about the edge structure associated to the graph.
However, the edge data is essential in the definition of the Laplacian, which
is used in the construction of the series (21) through the heat operator. In
this section we highlight the role of the edge data in the construction.

We assume that an infinite graph $G$ satisfies assumptions (G1), (G2’) and the
following additional assumption (meaning that the graph is locally finite).

  * (G3)

Finiteness of the combinatorial vertex degree. For all $x\in VG$ the number of
$y\in VG$ such that $w_{xy}>0$ is finite.

We have the following proposition.

######  Proposition 9.

Let $G$ be a connected, undirected infinite graph satisfying assumptions (G1),
(G2’) and (G3) above. Let $H(x,y;t)$ be a function on $VG\times
VG\times[0,\infty)$ defined for all $x,y\in VG$ and all $t\in[0,\infty)$ by

$H(x,y;t):=\frac{1}{\theta(x)}\delta_{x=y}.$ (24)

Let $\delta_{x}(y)$ be defined as in (5). Then, $H(x,y;t)$ defined by (24) is
the parametrix of order $k=0$, and the heat kernel $H_{G}$ constructed when
using (24) as a parametrix is given by (4).

###### Proof.

The set $VG$ is discrete, so then $H(x,y;t)$ is continuous on $VG\times
VG\times[0,\infty)$ and smooth in $t$ for fixed $x$ and $y$. It is evident
that $H$ belongs to $L^{1}(\theta)$ in both space variables and, furthermore,
satisfies the initial condition (9). Trivially,

$L_{G,x}H(x,y;t)=\Delta_{G,x}H(x,y;t)=\frac{1}{\theta^{2}(x)}\left\\{\begin{array}[]{ll}\mu(x),&x=y;\\\
-w_{xy},&x\sim y\\\ 0,&\text{otherwise.}\end{array}\right.$ (25)

The function (25) is continuous on $VG\times VG\times[0,\infty)$, hence the
second condition for the parametrix in Definition 6 is fulfilled. Moreover,
$\Delta_{G,x}H(x,\cdot;t)\in L^{1}(\theta)$ because the sum

$\sum_{z\in VG}\theta(z)\Delta_{G,x}H(x,z;t)$

is a finite sum, by the assumption (G3). Since $\frac{\partial}{\partial
t}H(x,\cdot;t)\equiv 0$, we conclude that the third condition for the
parametrix is fulfilled. Finally, from (25) it is evident that for all $x,y\in
VG$ and all $t>0$ we have

$|L_{G,x}H(x,y;t)|\leq\frac{\mu(x)}{\theta^{2}(x)}\leq\frac{M}{\eta^{2}}.$

Therefore, $H(x,y;t)$ is a parametrix of order $k=0$.

The heat kernel, as constructed in Theorem 8 when using the parametrix $H$, is
given by

$H_{G}(x,y;t)=H(x,y;t)+\sum_{\ell=1}^{\infty}(-1)^{\ell}\left(H\ast(L_{G,x}H)^{\ast\ell}\right)(x,y;t)$
(26)

We have the following evaluation of the first few terms in the convolution
series (26). First,

$\displaystyle(H\ast L_{G,x}H)(x,y;t)$
$\displaystyle=\int\limits_{0}^{t}\sum_{z\in
VG}\theta(z)H(x,z;t-\tau)L_{G,z}H(z,y;\tau)d\tau=t\theta(x)\frac{\delta_{x}(y)}{\theta(x)}$
$\displaystyle=t\delta_{x}(y).$

Using that $\theta(z)L_{G,z}H(z,y;\tau)=\delta_{z}(y)$ we get

$\displaystyle(H\ast L_{G,x}H)\ast L_{G,x}H(x,y;t)$
$\displaystyle=\int\limits_{0}^{t}\sum_{z\in
VG}\theta(z)(t-\tau)\delta_{x}(z)L_{G,z}H(z,y;\tau)d\tau$
$\displaystyle=\frac{t^{2}}{2}\sum_{z\in VG}\delta_{x}(z)\delta_{z}(y).$

Next, when proceeding by induction, we deduce that

$\left(H\ast(L_{G,x}H)^{\ast\ell}\right)(x,y;t)=\frac{t^{\ell}}{\ell!}\sum_{z_{1},\ldots,z_{\ell-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y).$

The sum on the right-hand side is finite, since $\delta_{x}(y)$ is supported
on a finite set, due to (G3).

With all this, we conclude that the heat kernel on $G$ is given by (4). ∎

######  Example 10.

Consider the case when $G=\mathbb{Z}$, meaning the graph whose set of vertices
is the set of integers. The two vertices $x,y\in\mathbb{Z}$ are connected if
and only if $x-y\in\\{-1,1\\}$. For every $x\in G$, let the vertex weight be
$\theta(x)=1$, and assume all edges weights are also equal to one. Let us use
(4) to compute the heat kernel on $\mathbb{Z}$.

The product
$\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)$
in (4) is non-zero precisely when the sequence
$x=z_{0},z_{1},\ldots,z_{\ell-1},y=z_{\ell}\in\mathbb{Z}$ is such that
$z_{h}-z_{h-1}\in\\{-1,0,1\\}$ for all $h=1,\ldots,\ell$. Such a sequence can
be identified with an $\ell$-tuple $(a_{1},\ldots,a_{\ell})$ where
$a_{1},\ldots,a_{\ell}\in\\{-1,0,1\\}$.

For $x,y\in\mathbb{Z}$, let $j\geq 0$ be such that $x-y=j$; we will comment
later when $x-y=-j$. Then the $\ell$-tuple $(a_{1},\ldots,a_{\ell})$ must have
exactly $j$ places all with the values $1$. Assume that $k\geq 0$ is the
number of places $a_{h}$ in the $\ell$-tuple $(a_{1},\ldots,a_{\ell})$ which
are equal to zero. Then at the remaining $\ell-j-k$ places there must be the
same number of entries with $1$ and with $-1$; in particular, $k$ must be such
that $\ell-j-k$ is an even number, say $i$, so we have that $\ell-j-k=2i$.

Therefore, every $\ell$-tuple $(a_{1},\ldots,a_{\ell})$ corresponding to the
sequence $x=z_{0},z_{1},\ldots,z_{\ell-1},y=z_{\ell}\in\mathbb{Z}$ such that
$z_{h}-z_{h-1}\in\\{-1,0,1\\}$ and such that $x-y=j$ is uniquely determined by
$k$ places at which there are zeros, where $k$ is such that $\ell-k-j$ is
even, and by $i=\frac{1}{2}(\ell-k-j)$ places at which there are the numbers
$-1$. The remaining places all have the value $1$. The number of all such
$\ell$-tuples of elements from $\\{-1,0,1\\}$ is exactly

$\binom{\ell}{k}\binom{\ell-k}{i}=\frac{\ell!}{k!i!(\ell-k-i)!},$

where $\ell=k+j+2i$. For each such $\ell$-tuple, we have

$\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)=2^{k}\cdot(-1)^{j}=(-1)^{\ell+k}2^{k},$

where the last equality follows since $\ell-k-j$ is even, so
$(-1)^{j}=(-1)^{\ell-k}=(-1)^{\ell+k}$. Therefore, for $x-y=j\geq 0$

$\sum_{z_{1},\ldots,z_{\ell-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)=\underset{\ell-
k-j\text{ even}}{\sum_{i,k\geq
0\,\,k+j+2i=\ell}}(-1)^{\ell+k}\frac{\ell!}{k!i!(i+j)!}2^{k}.$

Finally, we get that

$\displaystyle H_{\mathbb{Z}}(x,y;t)$
$\displaystyle=\sum_{\ell=0}^{\infty}t^{\ell}\underset{\ell-k-j\text{
even}}{\sum_{i,k\geq 0\,\,k+j+2i=\ell}}\frac{1}{k!i!(j+i)!}(-2)^{k}$
$\displaystyle=\sum_{k=0}^{\infty}\frac{(-2t)^{k}}{k!}\cdot\sum_{i=0}^{\infty}\frac{t^{j+2i}}{i!(j+i)!}=e^{-2t}I_{j}(2t),$

where $I_{j}(2t)$ is the $I$-Bessel function, see [GR07], formula 8.445 with
$\nu=j$.

In the case $x-y=-j$, we reverse the roles of $1$ and $-1$ in the above
combinatorial argument, we get that $H_{\mathbb{Z}}(x,y;t)=e^{-2t}I_{j}(2t)$.
In summary, we have shown that from (4) one gets that the heat kernel on
$\mathbb{Z}$ is $H_{\mathbb{Z}}(x,y;t)=e^{-2t}I_{|x-y|}(2t)$, which was
previously established in Bednarchak’s thesis or essentially already in [Fe71,
p. 60], see also [CY97, Be03, KN06].

######  Example 11.

For $q\geq 2$, let $G=T_{q+1}$ be a $q+1$-regular tree with vertex weights
$\theta\equiv 1$. Each vertex is connected to $q+1$ vertices with edges, and
we assume the edge weights are all equal to $1$. Then $\delta_{x}(z)=(q+1)$ if
$z=x$, $\delta_{x}(z)=-1$ for the $q+1$ vertices $z$ adjacent to $x$ and
$\delta_{x}(z)=0$ otherwise. We note that the case $q=1$ is considered in the
previous example. Let us use (4) to compute the heat kernel on $T_{q+1}$.

The product
$\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(y)$
is non-zero if and only if $x=z_{0},z_{1},\ldots,z_{\ell-1},y=z_{\ell}$ are
such that each pair of neighbouring entries are either equal or adjacent. Let
$x,y\in T_{q+1}$ be such that their distance is $r\geq 0$. If $\ell\leq r$,
the product is obviously zero, so we may assume that $\ell\geq r$.

For any integer $j$ with $0\leq j\leq\ell-r$, let us assume that exactly $j$
of the $\ell$ values $\delta_{z_{i}}(z_{i+1})$ are equal to $(q+1)$. Those
values can be chosen in $\displaystyle\binom{\ell}{j}$ ways. For such
selection of $j$ points $z_{i}=z_{i+1}$, the sequence
$x=z_{0},z_{1},\ldots,z_{\ell-1},y=z_{\ell}$ becomes a walk of length $\ell-j$
from $x$ to $y$. Let us denote the number of such walks by $b_{\ell-j}(r)$.
Note that he number of walks depends only on the distance $r$ between $x$ and
$y$. Therefore, when including the values taken by $\delta_{x}(z)$, we get
that

$\displaystyle a_{\ell}(r)$ $\displaystyle=\sum_{z_{1},\ldots,z_{\ell-1}\in
VG}\delta_{x}(z_{1})\delta_{z_{1}}(z_{2})\cdot\ldots\cdot\delta_{z_{\ell-1}}(x)=\sum_{j=0}^{\ell-r}\binom{\ell}{j}(q+1)^{j}(-1)^{\ell-j}b_{\ell-j}(r)$
$\displaystyle=\sum_{j=r}^{\ell}\binom{\ell}{\ell-j}(q+1)^{\ell-j}(-1)^{j}b_{j}(r)=(q+1)^{\ell}\sum_{j=0}^{\ell}\binom{\ell}{j}(q+1)^{-j}(-1)^{j}b_{j}(r).$

In the last term, we have adopted the convention that the number of walks of
length $j<r$ between two points at distance $r$ to be equal to zero.
Therefore,

$(-1)^{\ell}a_{\ell}(r)=\sum_{j=0}^{\ell}\binom{\ell}{j}(-(q+1))^{\ell-j}b_{j}(r),$

so then we have that

$H_{T_{q+1}}(x,y;t)=e^{-(q+1)t}\sum_{k=0}^{\infty}b_{k}(r)\frac{t^{k}}{k!}.$

Let us further evaluate this expression.

The ordinary generating function for the number of walks $b_{k}(r)$ of length
$k$ on the $(q+1)$-regular tree, between two points at a distance $r$ is given
by

$f_{q+1}(t)=\frac{2q}{q-1+(q+1)\sqrt{1-4qt^{2}}}\left(\frac{1-\sqrt{1-4t^{2}}}{2qt}\right)^{r},$
(27)

see [McK83] and [RZ09]; For $r\geq 0$, the exponential generating function

$g_{q+1}(t):=e^{(q+1)t}H_{T_{q+1}}(x,y;t)$

of the sequence $\\{b_{k}(r)\\}_{k=0}^{\infty}$ can be expressed in terms of
the ordinary generating function in at least two different ways. In one
approach, we start with the identity

$t^{-1}f_{q+1}(t^{-1})=(\mathcal{L}g_{q+1})(t),$

which is valid for $|t|>2\sqrt{q}$ and where $\mathcal{L}$ denotes the Laplace
transform. With elementary algebraic manipulations, one obtains the identity
that

$(\mathcal{L}g_{q+1})(t)=\sum_{j=0}^{\infty}q^{-(r+2j)/2}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2j+r}\left(\frac{t-\sqrt{t^{2}-4q}}{2q}\right),$

which is valid for $|t|>2\sqrt{q}$. The identity

$\left(\frac{t-\sqrt{t^{2}-4q}}{2q}\right)=\frac{1}{\sqrt{t^{2}-4q}}\left(1-\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2}\right)$

yields that

$(\mathcal{L}g_{q+1})(t)=\frac{1}{\sqrt{t^{2}-4q}}\sum_{j=0}^{\infty}q^{-(r+2j)/2}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2j+r}\left(1-q^{-1}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2}\right),$

which is valid for $|t|>2\sqrt{q}$. Therefore,

$(\mathcal{L}g_{q+1})(t)=\frac{q^{-r/2}}{\sqrt{t^{2}-4q}}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{r}-(q-1)\sum_{j=1}^{\infty}\frac{q^{-(r+2j)/2}}{\sqrt{t^{2}-4q}}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2j+r}.$

From [GR07], section 17.13, formula 109 with $a=2\sqrt{q}$ and $\nu=r+2j$ for
$j=0,1,\ldots$ and Re$(t)>2\sqrt{q}$, we have that

$\mathcal{L}(I_{r+2j}(2\sqrt{q}x))(t)=\frac{1}{\sqrt{t^{2}-4q}}\left(\frac{t-\sqrt{t^{2}-4q}}{2\sqrt{q}}\right)^{2j+r}.$

From this, we conclude that

$e^{(q+1)t}H_{T_{q+1}}(x,y;t)=q^{-r/2}I_{r}(2\sqrt{q}t)-(q-1)\sum_{j=1}^{\infty}q^{-(r+2j)/2}I_{2j+r}(2\sqrt{q}t).$
(28)

The formula in (28) is precisely the expression for the heat kernel on a
$T_{q+1}$ which was first proved in [CJK15, Proposition 3.1].

As stated, the exponential generating function $g_{q+1}(t)$ and the ordinary
generating function $f_{q+1}(t)$ are related by the Laplace transform, meaning
that

$g_{q+1}(t)=\frac{1}{2\pi}\int\limits_{-\pi}^{\pi}f_{q+1}(te^{i\theta})\exp(e^{i\theta})d\theta,$

valid for $|t|<1/(2\sqrt{q})$. Using (27), one can employ elementary
manipulations of the integral and derive the integral expression for the heat
kernel $H_{T_{q+1}}(x,y;t)$ established in [CY99]. We will omit the details of
these computations.

##  6 Using a distance metric to construct a parametrix

In this section we will describe how to define further examples of a
parametrix for the heat kernel using a distance function on $G$. The examples
we develop come from different distance functions $d:VG\times
VG\rightarrow\mathbb{R}_{\geq 0}$, so we denote the parametrix by $H_{d}$. In
section 6.1 we define some metrics that can be used in the construction of
$H_{d}$, and in section 6.2 we give explicit examples of an associated
parametrix.

Throughout this section, we assume that an infinite graph $G$ satisfies
assumptions (G1), (G2’) and the following strengthening of the assumption
(G3):

  * (G3’)

Uniform boundedness of the combinatorial vertex degree. There exists a
positive integer $N$ such that for all $x\in VG$ the number of $y\in VG$ such
that $w_{xy}>0$ is bounded by $N$.

Assumption (G3’) is not unusual in the work that is related to properties of
operators on infinite weighted graphs. For example, it suffices to deduce
natural upper and lower bounds for the heat kernel in terms of the
combinatorial distance in [MS00] and [Sc02]. Moreover, uniform boundedness of
the combinatorial degree yields essential self-adjointness of the Laplacian,
as well as of other operators on $G$, such as a Schrödinger operator. For more
details, we refer to [CdVT-HT11] or [Mi11].

###  6.1 Distance metric on a weighted graph

Let $d_{G}(x,y)$ denote an arbitrary distance metric on $G$ which is uniformly
bounded from below. More specifically, we assume there is a positive constant
$\delta$ such that

$\text{\rm for all $x,y\in VG$ \,\, we have
that}\,\,\,\,\,d_{G}(x,y)\geq\delta>0.$ (29)

Such a metric always exists on a connected graph, and below in this section,
as well as in section 7.1, we will provide a few examples.

####  6.1.1 Combinatorial graph distance

The graph $G$ is connected, meaning for any two distinct points $x,y\in VG$
there exists a path connecting the $x$ to $y$. To be clear, by a path we mean
a sequence of points $p(x,y)=\\{x=x_{0},x_{1},\ldots,x_{n}=y\\}$ such that
$w_{x_{j}x_{j+1}}>0$ for all $j\geq 0$. The path
$p(x,y)=\\{x=x_{0},x_{1},\ldots,x_{n}=y\\}$ is of length $n\in\mathbb{N}$ . If
$d_{G}(x,y)$ denotes the minimal length of all paths that connect $x$ and $y$,
it is then straightforward to conclude that $d_{G}$ is a distance metric on
$G$. Indeed, $d_{G}$ is well defined because $G$ is connected. The function
$d_{G}$ is symmetric, which follows from the fact that $G$ is undirected.
Also, the triangle inequality is immediate, while the equivalence
$d_{G}(x,y)=0$ if and only if $x=y$ follows from the fact that $G$ has no
loops.

This distance metric will be called the _combinatorial graph distance_. It is
obviously satisfies (29) with $\delta=1$.

The combinatorial graph distance is _intrinsic_ metric on $G$ (as defined in
[FLW14]) if and only if the condition (G3’) is fulfilled, see [HKMW13] and
[KLSW15].

####  6.1.2 Metric adapted to the Laplacian

There are another choices for a metric on $G$ which in addition to satisfying
(29) is closely related to stochastic properties of a graph. For example, _the
normalized combinatorial graph distance_ metric is defined by

$\rho_{G}:=(A(G,w,\theta))^{-1/2}d_{G};$

see (8) and section 6.1.1. It is immediate that $\rho_{G}$ is bounded from
below by $\delta=(M/\eta)^{-1/2}$. The metric $\rho_{G}$ is _adapted to the
Laplacian_ $\Delta_{G}$, in view of the Definition (1.3) on p. 117 of [Fo13].
This means that for all $x\in VG$, the metric $\rho_{G}$ satisfies the
inequality

$\frac{1}{\theta(x)}\sum_{y\sim x}\rho_{G}^{2}(x,y)w_{xy}\leq 1$ (30)

and there exists a constant $c_{\rho_{G}}$ such that $\rho_{G}(x,y)\leq
c_{\rho_{G}}$ whenever $x\sim y$. The inequality (30) is analogous to the
geodesic distance $\rho$ on a Riemannian manifold which satisfies
$|\nabla\rho(x,\cdot)|\leq 1$. Any metric on $G$ adapted to the Laplacian is
intrinsic.

A further example of a metric on $G$ which is adopted to the Laplacian
$\Delta_{G}$ and uniformly bounded from below is defined as follows. For all
$x,y\in VG$, let

$\tilde{d}_{G}(x,y):=\inf\left\\{\sum_{e\in
p(x,y)}\min\\{1,u(e)\\}:p(x,y)\,\text{is a path joining
}\,x\,\text{and}\,y\right\\}$

where $e$ is an edge in the path and, if $x_{i}$ and $x_{i+1}$ are the
endpoints of the edge $e$, $u(e)$ is defined as

$u(e)=\left(\min\left\\{\frac{\theta(x_{i})}{\mu(x_{i})},\frac{\theta(x_{i+1})}{\mu(x_{i+1})}\right\\}\right)^{1/2}.$

###  6.2 Dilated Gaussian as a parametrix

Let $d:VG\times VG\to[0,\infty)$ denote any distance metric on $G$ satisfying
the assumption (29).

######  Proposition 12.

With the notation as above, let $H_{d}:VG\times
VG\times(0,\infty)\to[0,\infty)$ be defined as

$H_{d}(x,y;t):=\frac{1}{\sqrt{\theta(x)\theta(y)}}\exp(-(\theta(x)\theta(y)d^{2}(x,y))/t)$
(31)

and

$H_{d}(x,y;0)=\lim_{t\downarrow 0}H_{d}(x,y;t).$

Then $H_{d}$ is a parametrix for the heat operator on $G$ of order $k=0$.

###### Proof.

By assumption, the distance $d$ is bounded from below. From this it is
immediate that $H_{d}(x,y;t)$ is continuous function in $t$ and that
$H_{d}(x,y;0)=0$ satisfies (18). Trivially, $H_{d}(x,y;t)$ is smooth for
$t\in(0,\infty)$ and all $x,y\in VG$. By definition, $H_{d}$ is symmetric in
the two spatial variables. So, in order to prove integrability in each space
variable, it suffices to show that for all $y\in VG$ and $t>0$, we have that

$\sum_{x\in
VG}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\sqrt{\frac{\theta(x)}{\theta(y)}}\leq\frac{1}{\sqrt{\eta}}\sum_{x\in
VG}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\sqrt{\theta(x)}<\infty.$
(32)

First, we note that for all positive numbers $a$ and $u$, the inequality

$u\exp(-u^{2}a^{2})\leq\frac{1}{a\sqrt{2e}}$

follows from elementary calculus. When taking
$u=\sqrt{\theta(x)\theta(y)}d(x,y)$ for $x\neq y$ and $a=\frac{1}{\sqrt{2t}}$,
we get that

$\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{2t}\right)\sqrt{\theta(x)}\leq\sqrt{\frac{t}{e}}\frac{1}{\sqrt{\theta(y)}d(x,y)}\leq\frac{1}{\delta}\sqrt{\frac{t}{\eta
e}},$

where we used (G2’) and (29) to deduce the last inequality. Therefore,

$\sum_{x\in
VG}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\sqrt{\theta(x)}\leq\sqrt{\theta(y)}+\sqrt{\frac{t}{\eta
e}}\frac{1}{\delta}\sum_{x\in
VG\setminus\\{y\\}}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{2t}\right).$

It is left to prove that the series on the right-hand side of the above
equation converges. For this, note that when combining (G3’) with (29) we
conclude that for fixed $y$ on $G$ there are at most $N^{n+1}$ vertices $x\neq
y$ with distance $\leq(n+1)\delta$ from $y$. Therefore,

$\displaystyle\sum_{x\in
VG\setminus\\{y\\}}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{2t}\right)$
$\displaystyle=\sum_{n=1}^{\infty}\sum_{n\delta<d(x,y)\leq(n+1)\delta}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{2t}\right)$
$\displaystyle\leq\sum_{n=1}^{\infty}N^{n+1}\exp\left(-\frac{(\eta
n\delta)^{2}}{2t}\right)<\infty.$ (33)

This completes the proof that $H_{d}$ is integrable in both space variables.

Next, we want to show the second condition in Definition 6 of the parametrix
holds for $H_{d}$. By definition, for $t>0$ we have that

$\displaystyle L_{G,x}H_{d}(x,y;t)$
$\displaystyle=\frac{1}{\theta(x)}\sum_{z\sim
x}\left(\frac{1}{\sqrt{\theta(x)\theta(y)}}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\right.$
$\displaystyle\hskip
72.26999pt\left.-\frac{1}{\sqrt{\theta(z)\theta(y)}}\exp\left(-\frac{\theta(z)\theta(y)d^{2}(z,y)}{t}\right)\right)w_{xz}$
$\displaystyle+\frac{\theta(x)\theta(y)d^{2}(x,y)}{t^{2}\sqrt{\theta(x)\theta(y)}}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right).$
(34)

The sum on the right-hand side (34) is finite by (G3’), and each term extends
to a continuous function in $t\in[0,\infty)$. Therefore, the second condition
in Definition 6 is also fulfilled.

Going further, conditions (G1) and (G2’) yield that

$\displaystyle\left|\Delta_{G,x}H_{d}(x,y;t)\right|$
$\displaystyle\leq\frac{M}{\eta^{2}}\sum_{z\sim
x}\left(\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)+\exp\left(-\frac{\theta(z)\theta(y)d^{2}(z,y)}{t}\right)\right)$
$\displaystyle\leq\frac{2MN}{\eta^{2}}.$

For all $u,a>0$, we have that

$u^{2}a^{-2}\exp(-u^{2}/a)\leq\frac{1}{ae},$

and for $u>0$,

$\lim_{a\downarrow 0}u^{2}a^{-2}\exp(-u^{2}/a)=0.$

Upon taking $u=\sqrt{\theta(x)\theta(y)}d(x,y)$ and $a=t$, we get for $x\neq
y$ and $t\in(0,t_{0})$ that

$\displaystyle\frac{\theta(x)\theta(y)d^{2}(x,y)}{t^{2}\sqrt{\theta(x)\theta(y)}}$
$\displaystyle\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)$
$\displaystyle\leq\frac{1}{\eta}\frac{\theta(x)\theta(y)d^{2}(x,y)}{t^{2}}\exp\left(-\frac{(\sqrt{\theta(x)\theta(y)}d(x,y))^{2}}{t}\right)\leq\frac{C}{\eta},$

where $C$ is a constant depending only on $t_{0}$. When $x=y$, the third line
in (34) equals zero. With all this, we have proved that $L_{G,x}H_{d}(x,y;t)$
is bounded for $t\in(0,t_{0})$ by a constant depending only on $t_{0}$.

Finally, in order to prove that $H_{d}$ is the parametrix of order zero, it is
left to prove that $\Delta_{G,x}H_{d}(x,\cdot;t)$ and
$\frac{\partial}{\partial t}H_{d}(x,\cdot;t)$ are in $L^{1}(\theta)$ for $x\in
VG$, $t>0$. From (G1), (G2’) and (G3’) we get that

$\displaystyle\sum_{y\in VG}|\Delta_{G,x}H_{d}(x,y;t)|\theta(y)$
$\displaystyle\leq\frac{MN}{\eta^{3/2}}\sum_{y\in
VG}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\sqrt{\theta(y)}$
(35) $\displaystyle+\frac{M}{\eta^{3/2}}\sum_{z\sim x}\sum_{y\in
VG}\exp\left(-\frac{\theta(z)\theta(y)d^{2}(z,y)^{2}}{t}\right)\sqrt{\theta(y)}.$

In view of (G3’) and the symmetry of variables, it follows from (32) that all
series on the right-hand side (35) are finite. This proves that
$\Delta_{G,x}H_{d}(x,\cdot;t)\in L^{1}(\theta)$.

To complete the proof of the proposition it is left to show that

$\sum_{y\in
VG}\frac{\theta(x)\theta(y)d^{2}(x,y)}{t^{2}\sqrt{\theta(x)\theta(y)}}\exp\left(-\frac{\theta(x)\theta(y)d^{2}(x,y)}{t}\right)\theta(y)<\infty.$

The proof is completely analogous to the proof of (32), so we will omit
further details.

∎

######  Remark 13.

In Proposition 12 above, the choice of a distance metric was not specified.
Indeed, any distance metric $d$ which is uniformly bounded from below could be
used in the definition (31) for the parametrix. In other words, we can
construct the same heat kernel when using different distance metric on the
graph.

This is quite different from the Riemannian manifolds situation where the
construction of a parametrix already requires considerable local information
associated to the Laplacian; see, for example, section VI.4 of [Ch84]. In a
sense, the very general methods by which one can define a parametrix for an
infinite graph belongs to a class of geometric phenomena on the graph which
are somewhat unexpected if one were to view a graph as the discretization of a
manifold. For an extensive discussion of such phenomena we refer to [KLW21].

##  7 Concluding remarks

We will close this article with the following observations.

###  7.1 Edge-weighted graph distance

In order to satisfy condition (29), one could impose the following condition.

  * (E1)

Boundedness from below of the edge weight: There exists a positive integer
$\tilde{\delta}$ such that

$\inf\limits_{x,y\in VG;x\neq y}w_{xy}>\tilde{\delta}.$

Condition (E1) when combined with (G1) yields (G3’). As such, the parametrix
construction for the heat kernel described in the preceding section can be
carried out with a distance metric which satisfies conditions (G1), (G2’) and
(E1).

Assumption (E1) arises naturally in the context of metric graphs in which a
positive real number $\ell_{e}$ is associated to every edge $e=\\{x,y\\}$ of a
graph, so then $w_{xy}$ can be taken be equal $\ell_{e}$. The condition
$\inf_{e}\ell_{e}>0$ is then imposed in order to deduce that a connected
metric graph is actually a length metric space; see for example [BBI01] or
[St06].

With (E1) another distance on $G$ can be defined as follows. For any vertices
$x$ and $y$ and any path $p(x,y)=\\{x=x_{0},x_{1},\ldots,x_{n}=y\\}$
connecting points $x$ and $y$, the _weighted length_ of the path
$\ell_{w}(p(x,y))$ is defined by

$\ell_{w}(p(x,y)):=\sum_{j\geq 0}w_{x_{j}x_{j+1}}.$

Let

$\tilde{d}_{G}(x,y):=\inf_{p(x,y)}\ell_{w}(p(x,y))$

where the infimum is taken over all paths connecting $x$ and $y$. Since $G$ is
connected and $w_{xy}$ is uniformly bounded from below, the function
$\tilde{d}_{G}:VG\times VG\to[0,\infty]$ is a distance on $VG$ which can be
called the _edge-weighted distance_. For graphs satisfying (G1), (G2’) and
(E1) it is immediate that the dilated Gaussian $H_{\tilde{d}_{G}}$ defined by
(31) is a parametrix.

###  7.2 Construction of the resolvent kernel

The resolvent kernel, or the Green’s function, associated to the graph
Laplacian can be expressed as the Laplace transform of the heat kernel
(possibly truncated by the contribution from the eigenvalue zero), see e.g.
[CY00]. Applying the formula 3.478.4 of [GR07] with $\nu=p=1$, the expression
for the heat kernel with the “seed” $H_{d}$ can be used in order to deduce an
explicit expression for the resolvent kernel in terms of series of products of
$K$-Bessel functions with index $1$. We will exploit this construction of the
resolvent kernel in a subsequent article.

In case one is interested in computing the resolvent kernel of a subgraph
$G^{\prime}$ of an infinite graph $G$, one may start with the heat kernel
$H_{G}$ on $G$ as a parametrix and use it to derive the heat kernel on
$G^{\prime}$ as described in Theorem 8 above. Then, by taking the Laplace
transform of this expression (possibly truncated by the contribution from the
eigenvalue zero) one will be able to express the resolvent kernel on
$G^{\prime}$ in terms of the resolvent kernel on $G$, see e.g. [LNY22] for the
case of a subgraph of a complete graph.

###  7.3 Varying edge and vertex weights

For a given graph $G$, with the edge weights function $w$ let $H_{G,w}$ be the
heat kernel associated to the edge weights function $w$. Let $w^{\prime}$
denote another edge weights function on $G$, and $H_{G,w^{\prime}}$ be the
associated heat kernel. Then $H_{G,w}$ can be used as a parametrix for the
heat kernel on $(G,w^{\prime})$. In fact, the convolution series in Theorem 8
gives a precise formula for the difference

$H_{G,w^{\prime}}(x,y;t)-H_{G,w}(x,y;t).$

From this expression, it is possible to study the variation of the heat kernel
in $w$, from which one could study spectral invariants derived from the heat
kernel such as regularized determinants or asymptotic behavior as, say, one
edge weight approaches zero.

For a given graph $G$, with the vertex weights functions $\theta$,
$\theta^{\prime}$ let $H_{G,\theta}$, $H_{G,\theta^{\prime}}$ be the
corresponding heat kernels. Then,
$\sqrt{\frac{\theta(x)\theta(y)}{\theta^{\prime}(x)\theta^{\prime}(y)}}H_{G,\theta}(x,y;t)$
can be used as a parametrix for the heat kernel on $(G,\theta^{\prime})$.

## References

  * [Be03] D. Bednarchak: Geometric properties coded in the long-time asymptotics for the heat equation on $Z^{n}$, Proc. Amer. Math. Soc. 131 (2003), no. 7, 2261–2269.
  * [BBI01] D. Burago, Y. Burago, S. Ivanov: A course in metric geometry, Graduate Studies in Mathematics, 33, American Mathematical Society, Providence, RI, 2001.
  * [CHJSV23] C. A. Cadavid, P. Hoyos, J. Jorgenson, L. Smajlović, J. D. Vélez: On an approach for evaluating certain trigonometric character sums using the discrete time heat kernel, European J. Combin. 108 (2023), Paper No. 103635, 23 pp.
  * [Ch84] I. Chavel: _Eigenvalues in Riemannian geometry_ , Academic Press, 1984.
  * [CJK15] G. Chinta, J. Jorgenson, A. Karlsson: Heat kernels on regular graphs and generalized Ihara zeta function formulas, Monatsh. Math. 178 (2015), no. 2, 171–190.
  * [CJKS23] G. Chinta, J. Jorgenson, A. Karlsson, L. Smajlović: The parametrix construction of the heat kernel on a graph, arxiv preprint, arXiv:2308.04174.
  * [CY97] Chung, F. R. K.; Yau, S.-T. A combinatorial trace formula, Tsing Hua lectures on geometry & analysis (Hsinchu, 1990–1991), International Press, Cambridge, MA, 1997, 107Ð116.
  * [CY99] F. Chung, S. T. Yau: Coverings, heat kernels and spanning trees, Electron. J. Comb. 6 Research Paper vol. 12, p. 21 (1999).
  * [CY00] F. Chung, S. T. Yau: Discrete Green’s functions, J. Combin. Theory Ser. A 91 (2000), 191–214
  * [CdVT-HT11] Y. Colin de Verdiére, N. Torki-Hamza, F. Truc: Essential self-adjointness for combinatorial Schrödinger operators II - Metrically noncomplete graphs, Math. Phys. Anal. Geom. 14(1) (2011) 21–38.
  * [Da93] E. B. Davies: Large deviations for heat kernels on graphs, J. Lond. Math. Soc. 47 (1993), 65–72.
  * [Do84] J. Dodziuk: Elliptic operators on infinite graphs, Analysis, geometry and topology of elliptic operators: papers in honor of Krzysztof P. Wojciechowski, World Sci. Publ., Hackensack, NJ, 2006, 353–368.
  * [DM06] J. Dodziuk, V. Mathai: Kato’s inequality and asymptotic spectral properties for discrete magnetic Laplacians, The ubiquitous heat kernel, Contemp. Math., vol. 398, Amer. Math. Soc., Providence, RI, 2006, 69–81.
  * [Fe71] W. Feller: An introduction to probability theory and its applications. Vol. II. Second edition, John Wiley and Sons, Inc., New York-London-Sydney, 1971.
  * [Fo13] M.Folz: Gaussian upper bounds for heat kernels of continuous time simple random walks, Elec. J. Prob. 16 (2011), 1693–1722.
  * [Fo14] M.Folz: Volume growth and spectrum for general graph Laplacians, Math. Z. 276 (2014), no. 1-2, 115–131.
  * [FLW14] R. L. Frank, D. Lenz, D. Wingert: Intrinsic metrics for non-local symmetric Dirichlet forms and applications to spectral theory, J. Funct. Anal. 266 (2014), no. 8, 4765–4808.
  * [GJ18] D. Garbin, J. Jorgenson: Spectral asymptotics on sequences of elliptically degenerating Riemann surfaces, L’Enseignement Mathématique 64 (2018), 161–206.
  * [GR07] I. S. Gradshteyn, I. M. Ryzhik: _Table of integrals, series and products_. Elsevier Academic Press, Amsterdam, 2007\.
  * [Gr09] A. Grigor’yan: Heat kernel and analysis on manifolds, AMS/IP Studies in Advanced Mathematics, 47. American Mathematical Society, Providence, RI; International Press, Boston, MA, 2009.
  * [GLY22] A. Grigor’yan, Y. Lin, S.-T. Yau: Discrete tori and trigonometric sums, J. Geom. Anal. 32 (2022), no. 12, Paper No. 298, 17 pp.
  * [HKLW12] S. Haeseler, M. Keller, D. Lenz, R. Wojciechowski: Laplacians on infinite graphs: Dirichlet and Neumann boundary conditions, J. Spectr. Theory 2(4) (2012), 397–432.
  * [HSSS23] T. Hasegawa, H. Saigo, S. Saito, S. Sugiyama: Lattice sums of I-Bessel functions, theta functions, linear codes and heat equations, https://arxiv.org/abs/2311.06489.
  * [HNT06] M. D. Horton, D. B. Newland, A. A. Terras: The contest between the kernels in the Selberg trace formula for the $(q+1)$-regular tree. The ubiquitous heat kernel, 265–293, Contemp. Math., 398, Amer. Math. Soc., Providence, RI, 2006.
  * [Hu12] X. Huang: On uniqueness class for a heat equation on graphs, J. Math. Anal. Appl. 393 (2012), no. 2, 377–388.
  * [HKMW13] X.Huang, M. Keller, J. Masamune, R. K. Wojciechowski: A note on self-adjoint extensions of the Laplacian on weighted graphs J. Funct. Anal. 265 (2013), no. 8, 1556–1578.
  * [JKS23] J. Jorgenson, A. Karlsson, L. Smajlović: The resolvent kernel on the discrete circle and twisted cosecant sums, https://arxiv.org/abs/2305.00202.
  * [JoLa01] J. Jorgenson, S. Lang: The ubiquitous heat kernel, in: Mathematics Unlimited - 2001 and Beyond, ed. Enquist and Schmid, Springer-Verlag (2001) 655–684.
  * [KN06] A. Karlsson, M. Neuhauser: Heat kernels, theta identities, and zeta functions on cyclic groups. Topological and asymptotic aspects of group theory, Contemp. Math. 394, Amer. Math. Soc., Providence, RI, 2006, 177–189.
  * [KL12] M. Keller, D. Lenz: Dirichlet forms and stochastic completeness of graphs and subgraphs, J. Reine Angew. Math. 666 (2012), 189–223.
  * [KLMST16] M. Keller, D. Lenz, Daniel; F. Münch, M. Schmidt, A. Telcs: Note on short-time behavior of semigroups associated to self-adjoint operators. Bull. Lond. Math. Soc. 48 (2016), no. 6, 935–944.
  * [KLSW15] M. Keller, D. Lenz, M. Schmidt, M. Wirth: Diffusion determines the recurrent graph, Adv. Math. 269 (2015) 364–398.
  * [KLW21] M. Keller, D. Lenz, R. K. Wojciechowski: Graphs and Discrete Dirichlet Spaces, Grundlehren der mathematischen Wissenschaften, vol. 358, Springer, Cham, 2021.
  * [Mn07] P. Mnëv: Discrete path integral approach to the Selberg trace formula for regular graphs, Comm. Math. Phys. 274 (2007), no. 1, 233–241.
  * [LNY21] Y. Lin, S.-M. Ngai, S.-T. Yau: Heat kernels on forms defined on a subgraph of a complete graph. Math. Ann 380 (2021), no. 3-4, 1891–1931.
  * [LNY22] Y. Lin, S.-M. Ngai, S.-T. Yau: Green’s Function of a Subgraph of a Complete Graph, Int. Math. Res. Not. IMRN Vol. 2023, no. 13, 11145–11171.
  * [McK83] B. McKay: Spanning trees in regular graphs, European J. Combin. 4 (1983) 149–160.
  * [Mi11] O. Milatovic: Essential self-adjointness of magnetic Schrödinger operators on locally finite graphs, Integral Equations Operator Theory 71 (2011), no. 1, 13–27.
  * [Mi49] S. Minakshisundaram: A generalization of Epstein zeta functions. With a supplementary note by Hermann Weyl, Canad. J. Math, 1 (1949), 320–327.
  * [Mi53] S. Minakshisundaram: Eigenfunctions on Riemannian manifolds, J. Indian Math. Soc. (N.S.) 17 (1953), 159–165.
  * [MP49] S. Minakshisundaram, Å. Pleijel: Some properties of the eigenfunctions of the Laplace-operator on Riemannian manifolds, Canad. J. Math. 1 (1949), 242–256.
  * [MS00] B. Metzger, P. Stollmann: Heat kernel estimates on weighted graphs: Bull. London Math. Soc. 32 (2000) 477–483.
  * [Ro83] J.-P. Roth: Le spectre du laplacien sur un graphe, Théorie du potentiel (Orsay, 1983), 521–539, Lecture Notes in Math. 1096, Springer, Berlin, 1984.
  * [RZ09] E. Rowland, D. Zeilberger: On the number of walks on a regular Cayley tree, arXiv:0903.1877.
  * [Sc02] A. U. Schmidt: A note on heat kernel estimates on weighted graphs with two-sided bounds on the weights, Appl. Math. E-Notes 2 (2002) 25–28.
  * [St06] K.-T. Sturm: On the geometry of metric measure spaces. I, Acta Math. 196 (2006), 65–131.
  * [TW03] A. Terras, D. Wallace: Selberg’s trace formula on the k-regular tree and applications, Int. J. Math. Math. Sci. 8 (2003), 501–526.
  * [Wo09] R. K Wojciechowski: Heat kernel and essential spectrum of infinite graphs, Indiana Univ. Math. J. 58 (2009), 1419–1441.
  * [Wo21] R. K. Wojciechowski: Stochastic completeness of graphs: bounded Laplacians, intrinsic metrics, volume growth and curvature, J. Fourier Anal. Appl. 27 (2021), no. 2, Paper No. 30, 45 pp.

Jay Jorgenson
Department of Mathematics
The City College of New York
Convent Avenue at 138th Street
New York, NY 10031 U.S.A.
e-mail<EMAIL_ADDRESS>
Anders Karlsson
Section de mathématiques
Université de Genève
2-4 Rue du Liévre
Case Postale 64, 1211
Genève 4, Suisse
e-mail<EMAIL_ADDRESS>
and
Matematiska institutionen
Uppsala universitet
Box 256, 751 05
Uppsala, Sweden
e-mail<EMAIL_ADDRESS>
Lejla Smajlović
Department of Mathematics and Computer Science
University of Sarajevo
Zmaja od Bosne 35, 71 000 Sarajevo
Bosnia and Herzegovina
e-mail<EMAIL_ADDRESS>