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

Abstract

Let $G=(V,E)$ be a loopless graph and $\mathcal{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))=\frac{1}{{\prod }_{v\in V}{d}^2(v)}\sum _{T\subseteq \mathcal{T}(G)}[\prod _{e=xy\in T}d(x)d(y)][\prod _{e=uv\in 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.

arXiv commentWe want to withdraw this paper, since there are inappropriate expressions in the Abstract and Introduction