New Approach for Derivation of Recurrence Relation to Enumerate Spanning Trees

Abstract

In mathematics, one always tries to get new structures from given ones. This also applies to the realm of graphs, where one can generate many new graphs from a given set of graphs. In this work, using knowledge of structures of graph, we drive the explicit recurrence formulas for the number of spanning trees in the sequence of some graphs generated by transformations. A possible spanning trees at (n+1)th label are mapped into all possible spanning trees at nth level. The objective of the mapping is to show that a constant number of spanning trees (and#945;) at (n + 1)th level are mapped into a single image at nth label by comparing the diand#64256;erential among as the constant multiple (and#946;) of spanning trees at (n and#8722; 1)th level. Symbols and#964;(Wn), and#964;(Fn) and and#964;(Ln) are used for number of spanning trees of wheel graph, fan graph and ladder graph respectively. This thesis is devoted to study of counting of spanning trees of wheel graph Wn+1, fan graph Fn+1 and ladder graph Ln. This thesis is divide into 7 chapters with chapter 1 giving the general information. In chapter 2, a recurrence relation for number of spanning trees is derived by giving a partition into all possible spanning tree of the fan graph Fn+1 and mapping them into all possible spanning trees of the fan graph Fn and subsequently the diand#64256;erence between them into all possible spanning trees of Fnand#8722;1 by keeping in view a constant number of objects should be mapped into a single image and the balance amount is constant multiple of number of spanning trees of Fnand#8722;1 using the equation 8and#946; = 21and#945;and#8722;55 for integer and#945; and and#946; in the interval 1 and#8804; and#945; and#8804; 5. We veriand#64257;ed that for and#945; = 3 and and#946; = 1, equation 8and#946; = 21and#945;and#8722;55 has integer solution. As a consequence the resulted recurrence relation is newlineand#964;(Fn+1) = 3and#964;(Fn)and#8722;and#964;(Fnand#8722;1) In chapter 3, a sequence of diand#64256;erent properties of number of spanning trees of fan graph Fn denoted by and#964;(Fn) are derived in the form newlinenand#8722;4 X i=1 newlineand#964;(Fnand#8722;3and#8722;i) = and#964;(Fnand#8722;2)and#8722;2and#964;(Fnand#8722;3) newlinenand#8722;5 X i=1 newlineand#964;(Fnand#8722;3and#8722;i) = and#964;(Fnand#8722;2)and#8722;2and#964;(Fnand#8722;3)and#8722;1 newlinenand#8722;5 X i=1 newlineiand#964;(Fnand#8722;3and#8722;i) = and#964;(Fnand#8722;3)and#8722;(nand#8722;4) newline2 newlineand newlinenand#8722;1 X i=1 newlineiand#964;(Fnand#8722;i) = and#964;(Fn) newlineIn ch