Abstract
Let \(X=(V, E)\) be a finite regular graph and \(H_t(u, v), \, u, v \in V\), the heat kernel on X. We prove that, if the graph X is bipartite and has four distinct Laplacian eigenvalues, the ratio \(H_t(u, v)/H_t(u, u), \, u, v \in V,\) is monotonically non-decreasing as a function of t. The key to the proof is the fact that such a graph is an incidence graph of a symmetric 2-design.
Similar content being viewed by others
References
Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Universitext. Springer, New York (2012)
van Dam, E.R.: Regular graphs with four eigenvalues. Linear Algebra Appl. 226(228), 139–162 (1995)
van Dam, E.R., Spence, E.: Small regular graphs with four eigenvalues. Discrete Math. 189, 233–257 (1998)
Huang, X., Huang, Q.: On regular graphs with four distinct eigenvalues. Linear Algebra Appl. 512, 219–233 (2017)
Huang, X., Huang, Q.: On graphs with three or four distinct normalized Laplacian eigenvalues. Algebra Colloq. 26, 65–82 (2019)
Mohammadian, A., Tayfeh-Rezaie, B.: Graphs with four distinct Laplacian eigenvalues. J. Algebra. Combin. 34, 671–682 (2011)
Nica, B.: A note on normalised heat diffusion for graphs. Bull. Aust. Math. Soc. 102, 1–6 (2020)
Price, T. M.: An inequality for the heat kernel on an Abelian Cayley graph. Electron. Commun. Probab. 22, 8 (2017)
Regev, O., Shinkar, I.: A counterexample to monotonicity of relative mass in random walks. Electron. Commun. Probab. 21, 8 (2016)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This work is supported by JSPS KAKENHI Grant Number 19K23410.
Rights and permissions
About this article
Cite this article
Kubo, T., Namba, R. Monotonic Normalized Heat Diffusion for Regular Bipartite Graphs with Four Eigenvalues. Graphs and Combinatorics 38, 22 (2022). https://doi.org/10.1007/s00373-021-02424-4
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-021-02424-4