Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs |
| |
| Authors: | Fengming Dong Weigen Yan |
| |
| Affiliation: | 1. MATHEMATICS AND MATHEMATICS EDUCATION, NATIONAL INSTITUTE OF EDUCATION, NANYANG TECHNOLOGICAL UNIVERSITY, SINGAPORE;2. SCHOOL OF SCIENCES, JIMEI UNIVERSITY, XIAMEN, CHINA |
| |
| Abstract: | For any graph G, let  be the number of spanning trees of G,  be the line graph of G, and for any nonnegative integer r,  be the graph obtained from G by replacing each edge e by a path of length  connecting the two ends of e. In this article, we obtain an expression for  in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between  and  and gives an explicit expression  if G is of order  and size  in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on  for such a graph G. |
| |
| Keywords: | graph spanning tree line graph Cayley’ s foumula subdivision |
|
|
be the number of spanning trees of G, 
be the line graph of G, and for any nonnegative integer r, 
be the graph obtained from G by replacing each edge e by a path of length 
connecting the two ends of e. In this article, we obtain an expression for 
in terms of spanning trees of G by a combinatorial approach. This result generalizes some known results on the relation between 
and 
and gives an explicit expression 
if G is of order 
and size 
in which s vertices are of degree 1 and the others are of degree k. Thus we prove a conjecture on 
for such a graph G.