The normalized Laplacians on both k-triangle graph and k-quadrilateral graph with their applications

摘要

The k-triangle graph Tk(G) is obtained from a graph G by replacing each edge in G with k+1 parallel paths, in which one is of length 1 and each of the rest k paths is of length 2; whereas the k-quadrilateral graph Qk(G) is obtained from G by replacing each edge in G with k+1 parallel paths, in which one is of length 1 and each of the rest k paths is of length 3. In this paper, we completely determine the normalized Laplacian spectrum on Tk(G) (resp. Qk(G)) for any connected graph G, k ⩾ 2. As applications, the correlation between the degree-Kirchhoff index, the Kemeny’s constant and the number of spanning trees of Tk(G) (resp. Qk(G), the r-th iterative k-triangle graph Trk(G), the r-th iterative k-quadrilateral graph Qrk(G)) and those of G are derived. Our results extend those main results obtained in Xie et al. (2016) and Li and Hou (2017).