A simple formula for the number of spanning trees of line graphs

作者：Gong, Helin^*; Jin, Xian'an

来源：Journal of Graph Theory, 2018, 88(2): 294-301.

DOI：10.1002/jgt.22212

• electrical networks
• line graphs
• mesh-star transformation
• spanning trees
• subdivision

Suppose G=(V,E) is a loopless graph and Sk(G) is the graph obtained from G by subdividing each of its edges k (k0) times. Let T(G) be the set of all spanning trees of G, L(Sk(G)) be the line graph of the graph Sk(G) and t(L(Sk(G))) be the number of spanning trees of L(Sk(G)). By using techniques from electrical networks, we first obtain the following simple formula:
t(L(Sk(G))) = 1/Pi(v is an element of V) d(2)(v)
x Sigma t is an element of tau(G) e-xy is an element of E(T)Pi d(x)d(y)
Sigma TT(G)xyE(T)[d(u)+kd(u)d(v)+d(v)].
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].

• 出版日期2018-6
• 单位厦门大学