Constructing heat kernels on infinite graphs

Let [Formula: see text] be an infinite, edge-weighted and vertex-weighted graph, with certain reasonable restrictions which will be described in the paper. 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 kernel of a graph and any one of its subgraphs, or the wish to have an explicit expression of the heat kernel related to Gaussian-type estimates for any graph metric bounded from below. Assuming uniform boundedness of the combinatorial vertex degree, we show that a dilated Gaussian depending on any distance metric on [Formula: see text] which is uniformly bounded from below can be taken as a parametrix in our construction. We discuss several applications of parametrix construction. For example, assuming that the graph is locally finite, we express the heat kernel [Formula: see text] as a Taylor series with the lead term being [Formula: see text], where [Formula: see text] is the combinatorial distance between [Formula: see text] and [Formula: see text] and [Formula: see text] depends (explicitly) upon edge and vertex weights. In the case [Formula: see text] is the regular [Formula: see text]-tree with [Formula: see text], our construction reproves different explicit formulas in papers by Chung-Yau, Cowling–Meda–Setti, and Chinta–Jorgenson–Karlsson.