The Complexity of Octopus Graph, Friendship Graph, and Snail Graph

Abstract

Graphs are basic structures that represent objects with nodes and relationships between objects with edges. Trees are one of the parts studied in graph theory along with finding the number of spanning trees of a graph such as octopus graph, friendship graph, and snail graph. The complexity of an octopus graph is strongly dependent on the number and length of tentacles, the complexity of a friendship graph is dependent on the number of triangle cycles, and the complexity of a snail graph is dependent on the number of edges and vertices located in the shell-like part of the snail. To calculate the number of spanning trees (τ(G)) of a graph, various calculations can be used, such as the extension of Kirchhoff's formula. The extension of Kirchhoff's formula uses the determinant of the adjacency matrix and degree matrix of the graph complement of a graph. Therefore, this research applies the extension of Kirchhoff's formula to obtain the complexity of octopus graph, friendship graph, and snail graph. From the analysis, it is obtained that for any n≥2, the number of spanning trees of octopus graph and friendship graph are τ(O_n )=1/5 √5 [((3+√5)/2)^n-((3-√5)/2)^n ] and τ(F_n )=3^n and the number of spanning trees of snail graph is τ(SI_n )=2^(n+2)+3n∙2^(n-1) for n≥1.