NUMBER OF SPANNING TREES OF ITERATED TRIANGULATION OF A GRAPH

A triangulation of a graph , denoted by , is obtained from by replacing each edge in by a complete graph . In this study, the Laplacian polynomial of is investigated. Moreover, an explicit formula for the number of spanning trees of is determined based on the analysis of its Laplacian polynomial properties. Two complex networks and obtained by iterated triangulations executed to cycle graph are studied. Furthermore, we obtain exact formulas for the number of spanning trees of these complex networks. The validity of the proposed formulas is numerically tested by Matlab.