Normalized Laplacian Spectrum and Graph Invariant Formulas of Polygonized Graphs Based on Tridiagonal Matrices

The polygonized graph P n , k ( G ) is constructed from a simple connected graph G through a substitution process. During this process, each edge in G is replaced by one path of length 1 and k paths of length +1( n , k ≥ 1). Based on the properties of the determinants of tridiagonal matrices, we present a unified formula for computing the normalized Laplacian spectrum of P n , k ( G ) from that of G . Moreover, we offer explicit formulas for calculating the number of spanning trees, Kemeny’s constant, and the multiplicative degree−Kirchhoff index of P n , k ( G ). In the educational context of graph theory and linear algebra, determinants serve as a valuable tool for exploring relevant graph parameters.