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

2015/07/23 by Helin Gong, Gong, Helin, Xian’an Jin +1
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1507.06389

Abstract

Let G=(V,E) be a loopless graph and T(G) be the set of all spanning trees of G. Let L(G) be the line graph of the graph G and t(L(G)) be the number of spanning trees of L(G). Then, by using techniques from electrical networks, we obtain the following formula: t(L(G)) = \frac1∏_{v∈ V}d²(v)∑_{T⊆ T(G)}[∏_{e = xy∈ T}d(x)d(y)][∏_{e = uv∈ E\backslash T}[d(u)+d(v)]]. As a result, we provide a very simple and different proof of the formula on the number of spanning trees of some irregular line graphs, and give a positive answer to a conjecture proposed by Yan [J. Combin. Theory Ser. A 120 (2013) no. 7, 1642-1648]. By applying our formula we also derive the number of spanning trees of circulant line graphs.

Related

• Formulas counting spanning trees in line graphs and their extensions
• Counting the spanning trees of a directed line graph
• The spanning tree spectrum: improved bounds and simple proofs
• The number of spanning trees in circulant graphs, its arithmetic\n properties and asymptotic
• Counting Spanning Trees of Threshold Graphs