Asymptotic spectral distributions of distance-$k$ graphs of Cartesian product graphs
Volume 132 / 2013
Colloquium Mathematicum 132 (2013), 35-51
MSC: Primary 05C50; Secondary 05C12, 47A10, 81S25.
DOI: 10.4064/cm132-1-4
Abstract
Let $G$ be a finite connected graph on two or more vertices, and $G^{[N,k]}$ the distance-$k$ graph of the $N$-fold Cartesian power of $G$. For a fixed $k\ge 1$, we obtain explicitly the large $N$ limit of the spectral distribution (the eigenvalue distribution of the adjacency matrix) of $G^{[N,k]}$. The limit distribution is described in terms of the Hermite polynomials. The proof is based on asymptotic combinatorics along with quantum probability theory.
