Asymptotic spectral distributions of distance-$k$ graphs of Cartesian product graphs

Volume 132 / 2013

Yuji Hibino, Hun Hee Lee, Nobuaki Obata Colloquium Mathematicum 132 (2013), 35-51 MSC: Primary 05C50; Secondary 05C12, 47A10, 81S25. DOI: 10.4064/cm132-1-4


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.


  • Yuji HibinoDepartment of Mathematics
    Saga University
    Saga, 840-8502, Japan
  • Hun Hee LeeDepartment of Mathematical Sciences and
    Research Institute of Mathematics
    Seoul National University
    Seoul 151-747, Republic of Korea
  • Nobuaki ObataGraduate School of Information Sciences
    Tohoku University
    Sendai, 980-8579, Japan

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image