Advances and Applications in Discrete Mathematics

The Advances and Applications in Discrete Mathematics is a prestigious peer-reviewed journal indexed in the Emerging Sources Citation Index (ESCI). It is dedicated to publishing original research articles in the field of discrete mathematics and combinatorics, including topics such as graphs, coding theory, and block design. The journal emphasizes efficient and powerful tools for real-world applications and welcomes expository articles that highlight current developments in the field.

Submit Article

NUMBER OF SPANNING TREES OF ITERATED TRIANGULATION OF A GRAPH

Authors

  • F. El-Safty
  • A. W. Aboutahoun

Keywords:

Laplacian polynomial, number of spanning trees, complex network

DOI:

https://doi.org/10.17654/0974165825001

Abstract

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_3$. 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 $H_t^n$ and $M_t^n$ 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.

Received: July 20, 2024
Accepted: September 18, 2024

References

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.

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.

J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, The Macmillan Press Ltd, 1976.

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.

D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, 1980.

J. Ge, Effective resistances and spanning trees in the complete bipartite graph plus a matching, Discrete Appl. Math. 305 (2021), 145-153.

I. Gutman, R. B. Mallion and J. W. Essam, Counting the spanning trees of a labeled molecular-graph, Molecular Physics 50 (1983), 859-877.

G. Iacobelli, D. R. Figueiredo and V. C. Barbosa, Counting trees with random walks, Expo. Math. 37 (2019), 96-102.

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.

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.

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.

D. Li and W. Yan, Counting spanning trees with a Kekulé structure in linear hexagonal chains, Appl. Math. Comput. 456 (2023), ID 128125.

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.

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.

A. S. Mata, Complex networks: a mini-review, Brazilian Journal of Physics 50 (2020), 658-672.

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.

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.

J. Wei and J. Wang, Spectra of complemented triangulation graphs, Mathematics 10 (2022), ID 3168.

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.

F. Z. Zhang, The Schur Complement and its Applications, Springer, 2005.

Downloads

Published

2024-11-07

Issue

Vol. 42 No. 1 (2025)

Section

Articles

License

Copyright (c) 2025 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

_________________________

Licensing Terms:

Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.

Contact Pushpa Publishing House for more info or permissions.

How to Cite

NUMBER OF SPANNING TREES OF ITERATED TRIANGULATION OF A GRAPH. (2024). Advances and Applications in Discrete Mathematics, 42(1), 1-16. https://doi.org/10.17654/0974165825001

Similar Articles

1-10 of 139

You may also start an advanced similarity search for this article.