A simple formula for the number of spanning trees of line graphs
Helin Gong, Xian’an Jin · Journal of Graph Theory · 2017
Abstract Suppose is a loopless graph and is the graph obtained from G by subdividing each of its edges k ( ) times. Let be the set of all spanning trees of G, be the line graph of the graph and be the number of spanning trees of . By using techniques from electrical networks, we first obtain the following simple formula: urn:x-wiley:03649024:media:jgt22212:jgt22212-math-0009 Then we find it is in fact equivalent to a complicated formula obtained recently using combinatorial techniques in [F. M. Dong and W. G. Yan, Expression for the number of spanning trees of line graphs of arbitrary connected graphs, J. Graph Theory. 85 (2017) 74–93].