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

preprint2015arXivOpen access

Abstract

Let G=(V,E)G=(V,E) be a loopless graph and T(G)\mathcal{T}(G) be the set of all spanning trees of GG. Let L(G)L(G) be the line graph of the graph GG and t(L(G))t(L(G)) be the number of spanning trees of L(G)L(G). Then, by using techniques from electrical networks, we obtain the following formula: t(L(G))=1∏v∈Vd2(v)∑T⊆T(G)[∏e=xy∈Td(x)d(y)][∏e=uv∈E\T[d(u)+d(v)]]. t(L(G)) = \frac{1}{\prod_{v\in V}d^2(v)}\sum_{T\subseteq \mathcal{T}(G)}\big[\prod_{e = xy\in T}d(x)d(y)\big]\big[\prod_{e = uv\in E\backslash T}[d(u)+d(v)]\big]. 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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.