Enumeration, classification and counting of spanning trees in plane 3-trees

Abstract

In this thesis, Graph theory has been studied extensively, particularly the properties of plane 3-trees of spanning trees of a graph. As plane 3-tree is a special class of graphs, we have tried to find a way to count the total number of spanning trees beside the classical Matrix Tree Theorem.

Our main aim is to generate the spanning trees of G_(n+1) from the set of spanning trees of G_n and classify them into two classes which are inductive and non-inductive.

A novel approach i.e., LU Factorization has been proposed to count all the possible spanning trees of plane 3-trees. By deriving a square matrix from a plane 3-tree, the counting part can be efficiently solved for any vertex in the graph. The results of our proposed approach have been analyzed through the result of the Kirchhoff Matrix Tree Theorem.

Alongside this approach, a verified algorithm has been proposed that has yielded the same result as our suggested approach. Through this algorithm, now we can closely observe the increasing nature of spanning trees of G_(n+1) from the set of spanning trees of G_n.

In addition, a unique approach (particularly for plane 3-tree) to count all the possible spanning trees for ‘n’ vertices of plane 3-trees has been proposed. The proposed conjecture’s result has been expressed exactly in the same as the result of the established algorithm and the traditional formula.

With the help of two new recurrence relations, we are now able to trace any number of spanning trees, both inductive and non-inductive. The theoretical behavior of these algorithms is thoroughly analyzed, and comparisons are made.