Complexity of Graphs with Wheel Graph and Fan Graph  as their Blocks

Alexander Alexander; Fransiskus Fran; Nilamsari Kusumastuti

doi:10.31764/jtam.v9i4.32776

Complexity of Graphs with Wheel Graph and Fan Graph as their Blocks

Alexander Alexander, Fransiskus Fran, Nilamsari Kusumastuti

Abstract

The complexity of a graphs remains an active area of research within graph theory. Let G be an undirected connected graph. Graph G is said as a non-separable graph if it does not have cut-vertex. A maximal non-separable subgraph of graph G is called a block of G. Every connected graph G has at least one spanning tree. The complexity of the graph G is the number of spanning trees in G, denoted by τ(G), and can be determined using the matrix tree theorem. The matrix used in this theorem is the Laplacian matrix, which related to the number of spanning trees in a graph. This research aims to formulate the complexity of graphs with wheel graph W_n and fan graph F_n as their blocks. The focus of this research is on graphs whose blocks are wheel graph W_n and fan graph F_n, specifically the m-wheel graph W_(n,m), the dragonfly graph 〖Dg〗_n, and the generalized dragonfly graph 〖Dg〗_n^((3,3) ). This study utilizes a qualitative and theoretical approach grounded in mathematical analysis. It involves a thorough review of relevant books and journal articles. The theoretical contributions of this research include deeper understanding about complexity of graph and elucidating the relationship between the complexity of graphs and their blocks. In this research, the complexity of graphs is determined using the matrix tree theorem, which involves calculating the cofactor of the Laplacian matrix. Based on τ(W_n ) and τ(F_n ), the results obtained in this study are τ(W_(n,m) )=(τ(W_n ))^m, τ(〖Dg〗_n )=(τ(F_(n+2) ))^2 and τ(〖Dg〗_n^((3,3) ) )=(τ(F_(n+2) ))^3 . The results of this study show that the complexity of a graph is related to the complexity of its blocks.

Keywords

Spanning Tree; Laplacian Matrix; Matrix Tree Theorem; Block of Graph.

Full Text:

DOWNLOAD [PDF]

References

Bača, M., Kimáková, Z., Lascsáková, M., & Semaničová-Feňovčíková, A. (2021). The Irregularity and Modular Irregularity Strength of Fan Graphs. Symmetry, 13(4), 605. https://doi.org/10.3390/sym13040605

Budi, H., Tirta, I., Agustin, I., Kristiana, A., & others. (2021). On rainbow antimagic coloring of graphs. Journal of Physics: Conference Series, 1832(1), 012016. https://doi.org/10.1088/1742-6596/1832/1/012016

Daoud, S. N. (2015). The deletion-contraction method for counting the number of spanning trees of graphs. The European Physical Journal Plus, 130(10), 217. https://doi.org/10.1140/epjp/i2015-15217-y

Daoud, S. N. (2017). Complexity of graphs generated by wheel graph and their asymptotic limits. Journal of the Egyptian Mathematical Society, 25(4), 424–433. https://doi.org/10.1016/j.joems.2017.07.005

Daoud, S. N. (2018). Complexity of Join and Corona graphs and Chebyshev polynomials. Journal of Taibah University for Science, 12(5), 557–572. https://doi.org/10.1080/16583655.2018.1502486

Daoud, S. N. (2019). Number of spanning trees of some families of graphs generated by a triangle. Journal of Taibah University for Science, 13(1), 731–739. https://doi.org/10.1080/16583655.2019.1626074

Daoud, S. N., & Mohamed, K. (2017). The complexity of some families of cycle-related graphs. Journal of Taibah University for Science, 11(2), 205–228. https://doi.org/10.1016/j.jtusci.2016.04.002

Daoud, S. N., & Saleh, W. (2020). Complexity trees of the sequence of some nonahedral graphs generated by triangle. Heliyon, 6(9). https://doi.org/10.1016/j.heliyon.2020.e04786

Deen, M. R. Z. E. (2023). Enumeration of spanning trees in prisms of some graphs. Proyecciones (Antofagasta), 42(2), 339–391. https://doi.org/10.22199/issn.0717-6279-4664

Deen, M. R. Z. E., & Aboamer, W. A. (2021). Complexity of Some Duplicating Networks. IEEE Access, 9, 56736–56756. https://doi.org/10.1109/access.2021.3059048

Deen, M. R. Z. E., Aboamer, W. A., & El-Sherbiny, H. M. (2023). The Complexity of the Super Subdivision of Cycle-Related Graphs Using Block Matrices. Computation, 11(8), 162. https://doi.org/10.3390/computation11080162

Fikadila, L., Kusumastuti, N., & Pasaribu, M. (2024). Penentuan Banyaknya Pohon Perentang Menggunakan Teorema Pohon Matriks. Bimaster: Buletin Ilmiah Matematika, Statistika Dan Terapannya, 13(2), 259–266. https://doi.org/10.26418/bbimst.v13i2.77239

Fran, F., Alexander, Yundari, Romanda, P., & Febyolga, E. (2024). The Complexity of Octopus Graph, Friendship Graph, and Snail Graph. EduMatSains : Jurnal Pendidikan, Matematika Dan Sains, 9(1), 84–101. https://doi.org/10.33541/edumatsains.v9i1.6042

Fran, F., Yundari, Hanssen, C., & Nurliantika. (2025). The complexity of triangular book graph, butterfly graph, lintang graph, and cycle books graph. AIP Conference Proceedings, 3142(1), 020088. https://doi.org/10.1063/5.0262263

Hanssen, C., Fran, F., & Yundari. (2024). The Complexity of Pencil Graph and Line Pencil Graph. PYTHAGORAS Jurnal Pendidikan Matematika, 19(2), 115–125. https://doi.org/10.21831/pythagoras.v19i2.77747

Holzer, F. (2022). Matrix tree theorems [Diploma Thesis]. TU Wien.

Inayah, N., Erfanian, A., & Korivand, M. (2022). Total Product and Total Edge Product Cordial Labelings of Dragonfly Graph (Dgn). Journal of Mathematics, 2022(1), 1–6. https://doi.org/10.1155/2022/3728344

Koutrouli, M., Karatzas, E., Paez-Espino, D., & Pavlopoulos, G. A. (2020). A Guide to Conquer the Biological Network Era Using Graph Theory. Frontiers in Bioengineering and Biotechnology, 8, 34. https://doi.org/10.3389/fbioe.2020.00034

Li, B., Broersma, H., & Zhang, S. (2018). Conditions for graphs to be path partition optimal. Discrete Mathematics, 341(5), 1350–1358. https://doi.org/10.1016/j.disc.2018.02.011

Liu, J.-B., & Daoud, S. N. (2018). The Complexity of Some Classes of Pyramid Graphs Created from a Gear Graph. Symmetry, 10(12), 689. https://doi.org/10.3390/sym10120689

Liu, J.-B., & Daoud, S. N. (2019). Number of Spanning Trees in the Sequence of Some Graphs. Complexity, 2019(1), 4271783. https://doi.org/10.1155/2019/4271783

Liu, J.-B., Munir, M., Yousaf, A., Naseem, A., & Ayub, K. (2019). Distance and Adjacency Energies of Multi-Level Wheel Networks. Mathematics, 7(1), 43. https://doi.org/10.3390/math7010043

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

Nurliantika, N., Fran, F., & Yundari. (2025). Determinants of Tridiagonal and Circulant Matrices Special Form by Chebyshev Polynomials. JTAM (Jurnal Teori Dan Aplikasi Matematika), 9(1), 190–205. https://doi.org/10.31764/jtam.v9i1.27871

Shang, Y. (2016). On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs. Open Mathematics, 14(1), 641–648. https://doi.org/10.1515/math-2016-0055

Sun, W., Wang, S., & Zhang, J. (2016). Counting spanning trees in prism and anti-prism graphs. Journal of Applied Analysis & Computation, 6(1), 65–75. https://doi.org/10.11948/2016006

Wei, Y., Gao, Z., & Lu, X. (2023). The Complexity of Wheel Graphs with Multiple Edges and Vertices. Asian Research Journal of Mathematics, 19(9), 1–12. https://doi.org/10.9734/arjom/2023/v19i9694

DOI: https://doi.org/10.31764/jtam.v9i4.32776