Counting Spanning Trees Of Two Families Of Graphs

Given an arbitrary edge-weighted graph G=（V（G）,E（G））together with an edge-weighted functionω:E（G）→（0,+∞）,if the weight of each edge of G is regarded as the conductance of this edge,then this edge-weighted graph can be equivalent to an electrical network in physics.Let T（G）be the set of spanning trees of G.For any T∈T（G）,the weight of T is defined as the product of weights of edges in T,i.e.,ω（T）=∏_e∈E（G）ω（e）.The summation of weights of spanning trees of G is denoted by t（G）,that is,t（G）=∑_T∈T（G）ω（T）.Obviously,if the edge-weighted function ω≡1,then t（G）is the number of spanning trees of G.By using electrically equivalent principle of substitution,generalized Wye-Delta trans-formation and series-parallel rules,et al.,firstly,we give the definition of the（edge-weighted）line graph of an edge-weighted graph,and we study its enumerative problem of weighted spanning trees and obtain some formulae for the sum of weights of spanning trees of line graphs of edge-weighted graphs,which generalize the corresponding results on enumeration of spanning trees of graphs with ω≡1.Secondly,we study the enumerative problem on counting spanning trees of the so-called generalized Farey graphs which is related closely to statistical physics.Finally,we give a simple proof of the well known Foster’s first theorem in electrical network theory.