A triangulation of a graph G, denoted by T(G), is obtained from G by replacing each edge in G by a complete graph K₃. In this study, the Laplacian polynomial of T(G) is investigated. Moreover, an explicit formula for the number of spanning trees of T(G) is determined based on the analysis of its Laplacian polynomial properties. Two complex networks and obtained by iterated triangulations executed to cycle graph C_n  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.

Laplacian polynomial, number of spanning trees, complex network

Received: July 20, 2024; Accepted: September 18, 2024; Published: November 7, 2024

How to cite this article: F. El-Safty and A. W. Aboutahoun, Number of spanning trees of iterated triangulation of a graph, Advances and Applications in Discrete Mathematics 42(1) (2025), 1-16. https://doi.org/10.17654/0974165825001

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:
[1] S. B. B. Altindag, I. Milovanovic and E. Milovanovic, Laplacian coefficients, Kirchhoff index and the number of spanning trees of graphs, Asian-European Journal of Mathematics 17 (2024), ID 2450033. https://doi.org/10.1142/S1793557124500335.
[2] T. Atajan and H. Inaba, Network reliability analysis by counting the number of spanning trees, IEEE International Symposium on Communications and Information Technology 1 2004, pp. 601-604.
[3] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, The Macmillan Press Ltd, 1976.
[4] T. J. N. Brown, R. B. Mallion, P. Pollak and A. Roth, Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes, Discrete Appl. Math. 67 (1996), 51-66.
[5] D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, 1980.
[6] J. Ge, Effective resistances and spanning trees in the complete bipartite graph plus a matching, Discrete Appl. Math. 305 (2021), 145-153.
[7] I. Gutman, R. B. Mallion and J. W. Essam, Counting the spanning trees of a labeled molecular-graph, Molecular Physics 50 (1983), 859-877.
[8] G. Iacobelli, D. R. Figueiredo and V. C. Barbosa, Counting trees with random walks, Expo. Math. 37 (2019), 96-102.
[9] A. K. Kelmans and V. M. Chelnokov, Certain polynomials of a graph and graphs with an extremal number of trees, J. Combin. Theory Ser. B 16 (1974), 197-214.
[10] G. Kirchhoff, Ueber die Auflosung der Gleichungen, auf welche man bei der Untersuchung der Linearen Ver theilung galvanischer Strome gefuhrt wird, Annelen Der Physik Und Chemie 12 (1847), 497-508.
[11] Z. Kosar, S. Zaman, W. Ali and A. Ullah, The number of spanning trees in a K5 chain graph, Phys. Scr. 98 (2023), ID 125239.
[12] D. Li and W. Yan, Counting spanning trees with a Kekulé structure in linear hexagonal chains, Appl. Math. Comput. 456 (2023), ID 128125.
[13] F. Ma, J. Su, Y. Hao, B. Yao and G. Yan, A class of vertex-edge-growth small-world network models having scale-free, self-similar and hierarchical characters, Phys. A 492 (2018), 1194-1205.
[14] F. Ma and B. Yao, An iteration method for computing the total number of spanning trees and its applications in graph theory, Theoret. Comput. Sci. 708 (2018), 46-57.
[15] A. S. Mata, Complex networks: a mini-review, Brazilian Journal of Physics 50 (2020), 658-672.
[16] R. Mokhlissi, D. Lotfi, J. Debnath and M. El Marraki, Complexity analysis of small-world networks and spanning tree entropy, Complex Networks and their Applications V, H. Cherifi et al. eds., Springer International Publishing, 2017, pp. 197-208.
[17] W. Wang, D. Yang and Y. Luo, The Laplacian polynomial and Kirchhoff index of graphs derived from regular graphs, Discrete Appl. Math. 161 (2013), 3063-3071.
[18] J. Wei and J. Wang, Spectra of complemented triangulation graphs, Mathematics 10 (2022), ID 3168.
[19] P. Xie, Z. Zhang and F. Comellas, On the spectrum of the normalized Laplacian of iterated triangulations of graphs, Appl. Math. Comput. 273 (2016), 1123-1129.
[20] F. Z. Zhang, The Schur Complement and its Applications, Springer, 2005.