The number of spanning trees in graphs (networks) is a crucial invariant, and it is also an important measure of the reliability of a network. Spanning trees are special subgraphs of a graph that have several important properties. First, T must span G, which means it must contain every vertex in graph G, if T is a spanning tree of graph G. T needs to be a subgraph of G, second. Stated differently, any edge present in T needs to be present in G as well. Third, G is the same as T if each edge in T is likewise present in G. In path-finding algorithms like Dijkstra's shortest path algorithm and A* search algorithm, spanning trees play an essential part. In those approaches, spanning trees are computed as component components. Protocols for network routing also take advantage of it. In numerous techniques and applications, minimum spanning trees are highly beneficial. Computer networks, electrical grids, and water networks all frequently use them. They are also utilized in significant algorithms like the min-cut max-flow algorithm and in graph issues like the travelling salesperson problem. In this paper, we use matrix analysis and linear algebra techniques to obtain simple formulas for the number of spanning trees of certain kinds of cyclic snake graphs.
| Published in | Mathematical Modelling and Applications (Volume 9, Issue 1) |
| DOI | 10.11648/j.mma.20240901.12 |
| Page(s) | 14-22 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2024. Published by Science Publishing Group |
Cyclic Snakes, Subdivision, Edge Contraction, Spanning Trees
| [1] | Colbourn, C. J. (1987). The combinatorics of network reliability. Oxford University Press, Inc. |
| [2] | Myrvold, W., Cheung, K. H., Page, L. B., & Perry, J. E. (1991). Uniformly-most reliable networks do not always exist. Networks, 21(4), 417-419. |
| [3] | Petingi, L., Boesch, F., & Suffel, C. (1998). On the characterization of graphs with maximum number of spanning trees. Discrete mathematics, 179(1-3), 155-166. |
| [4] | Brown, T. J., Mallion, R. B., Pollak, P., & Roth, A. (1996). Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes. Discrete Applied Mathematics, 67(1-3), 51-66. |
| [5] | Moon, J. W. (1967). Enumerating labelled trees. Graph theory and theoretical physics, 261271. |
| [6] | Kirchhoff, G. (1847). Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. Annalen der Physik, 148(12), 497-508. |
| [7] | Kelmans, A. K., & Chelnokov, V. M. (1974). A certain polynomial of a graph and graphs with an extremal number of trees. Journal of Combinatorial Theory, Series B, 16(3), 197-214. |
| [8] | Cayley, G. A. (1889). A Theorem on trees, Quarterly Journal of Mathematics, 23, 276–378. |
| [9] | Clark, L. (2003). On the enumeration of multipartite spanning trees of the complete graph. Bull. of the ICA, 38, 50-60. |
| [10] | Qiao, S. N., & Chen, B. (2009). The number of spanning trees and chains of graphs. Applied Mathematics E-Notes, 9, 10-16. |
| [11] | Sedlacek, J. (1970). On the skeletons of a graph or digraph. In Proc. Calgary International Conference on Combinatorial Structures and their Applications, Gordon and Breach (pp. 387-391). |
| [12] | Sedlácek, J. (1970). Lucas number in graph theory. Mathematics (Geometry and Graph theory) (Chech), Univ. Karlova, Prague, 111-115. |
| [13] | Boesch, F. T., & Bogdanowicz, Z. R. (1987). The number of spanning trees in a prism. International journal of computer mathematics, 21(3-4), 229-243. |
| [14] | Boesch, F. T., & Prodinger, H. (1986). Spanning tree formulas and Chebyshev polynomials. Graphs and Combinatorics, 2(1), 191-200. |
| [15] | S. N. Daoud, The deletion-contraction method for counting the number of spanning trees of graphs, Eur. Phys. J. Plus, 130, 2015, 1-14. |
| [16] | S. N. Daoud, Complexity of graphs generated by wheel graph and their asymptotic limits, JOEMS, 25(4), 2017, 424-433. |
| [17] | S. N. Daoud, Number of spanning trees in different products of complete and complete tripartite graphs, Ars Comb., 139, 2018, 85-103. |
| [18] | S. N. Daoud, Number of Spanning trees of cartesian and composition products of graphs and Chebyshev polynomials, IEEE Access, 7, 2019, 71142-71157. |
| [19] | J. B. Liu, and S. N. Daoud, The complexity of some classes of pyramid graphs created from a gear graph, Symmetry, 10(12), 2018. |
| [20] | S. N. Daoud and W. Saleh, Number of Spanning Trees of Some of Pyramid Graphs Generated by a Wheel Graph, Math. Comb, 43, 2020. |
| [21] | S. N. Daoud, Complexity of join and corona graphs and Chebyshev polynomials, Journal of Taibah University for Science, 12(5), 2018, 557-572. |
| [22] | B. Mohamed, L. Mohaisen and M. Amin, Binary Equilibrium Optimization Algorithm for Computing Connected Domination Metric Dimension Problem, Sci. Program, 2022. |
| [23] | B. Mohamed and M. Amin, The Metric Dimension of Subdivisions of Lilly Graph, Tadpole Graph and Special Trees," Appl. Comput. Math, 12(1), 2023, 9-14. |
| [24] | B. Mohamed, L. Mohaisen and M. Amin, Computing Connected Resolvability of Graphs Using Binary Enhanced Harris Hawks Optimization, Intell. Autom. Soft Comput, 36(2), 2023. |
| [25] | B. Mohamed, Metric Dimension of Graphs and its Application to Robotic Navigation, IJCA, 184(15), 2022. |
| [26] | B. Mohamed and M. Amin, Domination Number and Secure Resolving Sets in Cyclic Networks, Appl. Comput. Math, 12(2), 2023, 42-45. |
| [27] | B. Mohamed and M. Amin, A hybrid optimization algorithms for solving metric dimension problem, (GRAPH-HOC), 15(1), 2023, 1-10. |
| [28] | B. Mohamed, A Comprehensive Survey on the Metric Dimension Problem of Graphs and Its Types, Int. J. Theor. Appl. Math, 9(1), 2023, 1-5. |
| [29] | Chió, F. (1853). Mémoire sur les fonctions connues sous le nom De Résultantes Ou De Déterminans. éditeur inconnu. |
| [30] | Gjonbalaj, Q., & Salihu, A. (2010). Computing the determinants by reducing the orders by four. Applied Mathematics E-Notes, 10, 151-158. |
| [31] | Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. |
APA Style
Mohamed, B., Amin, M. (2024). Complexity of Some Types of Cyclic Snake Graphs. Mathematical Modelling and Applications, 9(1), 14-22. https://doi.org/10.11648/j.mma.20240901.12
ACS Style
Mohamed, B.; Amin, M. Complexity of Some Types of Cyclic Snake Graphs. Math. Model. Appl. 2024, 9(1), 14-22. doi: 10.11648/j.mma.20240901.12
AMA Style
Mohamed B, Amin M. Complexity of Some Types of Cyclic Snake Graphs. Math Model Appl. 2024;9(1):14-22. doi: 10.11648/j.mma.20240901.12
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.mma.20240901.12,
author = {Basma Mohamed and Mohamed Amin},
title = {Complexity of Some Types of Cyclic Snake Graphs},
journal = {Mathematical Modelling and Applications},
volume = {9},
number = {1},
pages = {14-22},
doi = {10.11648/j.mma.20240901.12},
url = {https://doi.org/10.11648/j.mma.20240901.12},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mma.20240901.12},
abstract = {The number of spanning trees in graphs (networks) is a crucial invariant, and it is also an important measure of the reliability of a network. Spanning trees are special subgraphs of a graph that have several important properties. First, T must span G, which means it must contain every vertex in graph G, if T is a spanning tree of graph G. T needs to be a subgraph of G, second. Stated differently, any edge present in T needs to be present in G as well. Third, G is the same as T if each edge in T is likewise present in G. In path-finding algorithms like Dijkstra's shortest path algorithm and A* search algorithm, spanning trees play an essential part. In those approaches, spanning trees are computed as component components. Protocols for network routing also take advantage of it. In numerous techniques and applications, minimum spanning trees are highly beneficial. Computer networks, electrical grids, and water networks all frequently use them. They are also utilized in significant algorithms like the min-cut max-flow algorithm and in graph issues like the travelling salesperson problem. In this paper, we use matrix analysis and linear algebra techniques to obtain simple formulas for the number of spanning trees of certain kinds of cyclic snake graphs.
},
year = {2024}
}
TY - JOUR T1 - Complexity of Some Types of Cyclic Snake Graphs AU - Basma Mohamed AU - Mohamed Amin Y1 - 2024/02/20 PY - 2024 N1 - https://doi.org/10.11648/j.mma.20240901.12 DO - 10.11648/j.mma.20240901.12 T2 - Mathematical Modelling and Applications JF - Mathematical Modelling and Applications JO - Mathematical Modelling and Applications SP - 14 EP - 22 PB - Science Publishing Group SN - 2575-1794 UR - https://doi.org/10.11648/j.mma.20240901.12 AB - The number of spanning trees in graphs (networks) is a crucial invariant, and it is also an important measure of the reliability of a network. Spanning trees are special subgraphs of a graph that have several important properties. First, T must span G, which means it must contain every vertex in graph G, if T is a spanning tree of graph G. T needs to be a subgraph of G, second. Stated differently, any edge present in T needs to be present in G as well. Third, G is the same as T if each edge in T is likewise present in G. In path-finding algorithms like Dijkstra's shortest path algorithm and A* search algorithm, spanning trees play an essential part. In those approaches, spanning trees are computed as component components. Protocols for network routing also take advantage of it. In numerous techniques and applications, minimum spanning trees are highly beneficial. Computer networks, electrical grids, and water networks all frequently use them. They are also utilized in significant algorithms like the min-cut max-flow algorithm and in graph issues like the travelling salesperson problem. In this paper, we use matrix analysis and linear algebra techniques to obtain simple formulas for the number of spanning trees of certain kinds of cyclic snake graphs. VL - 9 IS - 1 ER -
Mathematics and Computer Science Department, Faculty of Science, Menoufia University, Shebin Elkom, Egypt
