Complexity of Graphs with Wheel Graph and Fan Graph as their Blocks - Alexander, Alexander; Fran, Fransiskus; Kusumastuti, Nilamsari (Universitas Muhammadiyah Mataram, 2025)
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.