Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs

Fengming Dong, Weigen Yan

Published 2015-07-29Version 1

For any graph $G$, let $t(G)$ be the number of spanning trees of $G$, $L(G)$ be the line graph of $G$ and for any non-negative integer $r$, $S_r(G)$ be the graph obtained from $G$ by replacing each edge $e$ by a path of length $r+1$ connecting the two ends of $e$. In this paper we find a combinatorial approach to obtain %an expression for $t(L(G))$ and more generally an expression for $t(L(S_r(G)))$. Thus we generalize some known results on the relation between $t(L(G))$ and $t(G)$ and prove a conjecture that $t(L(S_1(G)))=k^{m+s-n-1}(k+2)^{m-n+1}t(G)$ for any graph $G$ of order $n+s$ and size $m+s$ in which $s$ vertices are of degree $1$ and the others are of degree $k$.