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

Unknown author(s)

Journal of Graph Theory · 2016 · 35 citations · 8 references

DOIFull text

Open access

Concepts

Abstract

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 .

References

8