On the normalized Laplacians with some classical parameters involving graph transformations

Abstract

Given a connected graph G, two types of graph transformations on G are considered. The graph $F\left(G\right)$ is obtained by applying the first transformation on G, i.e. it is formed by adding a new triangle $u_e{v}_e{w}_e$ for each edge e=uv in G and then adding in edges $u{u}_e$ and $v{v}_e$, whereas the graph $R\left(G\right)$ is obtained by applying the second transformation on G, i.e. it is formed by adding a new quadrangle $u_e{v}_e{w}_e{x}_e$ for each edge e=uv in G and then adding in edges $u{u}_e$ and $v{w}_e$. Repeating the above constructions r times yields the iterative graphs $F_r\left(G\right)$ and $R_r\left(G\right)$. In this paper, the normalized Laplacian spectrum of $F\left(G\right)$ (resp. $R\left(G\right)$) is completely determined in regards to G. As applications, the significant formula are obtained to calculate the multiplicative degree-Kirchhoff index, the Kemeny's constant and the number of spanning trees of the rth iterative graph $F_r\left(G\right)$ (resp. $R_r\left(G\right)$) compared to those of G, where $r⩾1$.

Keywords:

• Normalized Laplacian
• multiplicative degree-Kirchhoff index
• Kemeny's constant
• spanning tree

AMS subject classification:

• 05C50

Acknowledgements

The authors would like to express their sincere gratitude to all of the referees for their careful reading and insightful suggestions, which led to a number of improvements to this paper.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

J.L. acknowledges the financial support from the National Natural Science Foundation of China (Grant No. 61773020) and S.L. acknowledges the financial support from the National Natural Science Foundation of China (Grant Nos. 11671164, 11271149).