Hexagonal and k-hexagonal graph's normalized Laplacian spectrum and applications

Abstract

Substituting each edge of a simple connected graph $G$ by a path of length 1 and $k$ paths of length 5 generates the $k$-hexagonal graph $H^k(G)$. Iterative graph $H_n^k(G)$ is produced when the preceding constructions are repeated $n$ times. According to the graph structure, we obtain a set of linear equations, and derive the entirely normalized Laplacian spectrum of $H_n^k(G)$ when $k=1$ and $k⩾2$ respectively by analyzing the structure of the solutions of these linear equations. We find significant formulas to calculate the Kemeny's constant, multiplicative degree-Kirchhoff index and number of spanning trees of $H_n^k(G)$ as applications.