Generation And Count Of Spanning Trees Containing Certain Appointed Edges

In this paper, based on the classical spanning trees and counting problems as background,by means of the graph of matrix and broken cycles theorems,the generating and counting problems of the spanning tree with some precribed edges are studied.Firstly, the ring sum generating of matrix method for connected graphs of spanning trees containing some prescribed edges are given. After defining the notations of the ring complement incidence matrix and ring sum matrix, we give the proof of the matrix method for connected graphs of spanning trees containing some prescribed edges, namely, the ring sum generating of matrix method.Secondly, this paper gives a new method of the generation of all spanning trees containing some prescribed edges based on the classification. First, choosing one graph’s reference spanning tree containing all prescribed edges arbitrarily, according to the distance between other spanning trees containing all prescribed edges and the reference spanning tree,all spanning trees containing all prescribed edges except the reference spanning tree could be divided into d groups at most. The relation between the categorical spanning trees containing some prescribed edges and the fundamental broken cycles or ring sums of the broken is given and proved, which also illustrates this new method based on classification could obtain the generating graph of all spanning trees containing some prescribed edges which are different from others.Thirdly, this paper mainly discusses the counting problems for connected graph of containing one prescribed edge and only one edge, and we obtain the count’s formula of the total spanning with k-claw or only one edge of k-claw in a connected graph. We also exemplify the formula applied to a connected graph containing k-claw or only one edge of k-claw in the count of the total generation of spinning trees.