Generation And Count Of Spanning Trees In Special Graphs

Generation and counting problems of spanning trees of special graphs are studied by using combinatorial theory,Feussner Formula and Kirchhoff"s Matrix-tree Theorem.First, we present a new method of the generation of all spanning trees about edges contraction of a graph by using codatum of the basic cut sets. For a connected graphs, choosing one reference spanning tree To arbitrarily and appointing k edges as the specified edges of graph, we find out codatum of the basic cut sets of the specified edges.According to the codatum of the basic cut sets distance between other spanning trees and To, we get the generation of all spanning trees with the specified contractible edges of edges contraction graph.Secondly, the generation of spanning trees in some special graphs are introduced, namely, the flag map,Quadrilateral chain and Hexagon carriage graph. We give a new method of the generation of all spanning tress which is Polynomial multiplication. Then, the formula for number of spanning trees of these graphs is presented.Last, a simpler method to prove the count of spanning tree of the ladder graph by using Feussner’s Combinatorial Formula and Linear recursion of constant coefficient are given. Based on it, we also give the counting formula of spanning trees of the Composite diagram including the ladder graph and the complete graph.