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.