Counting the spanning trees of a directed line graph

Hoda Bidkhori, Shaunak Kishore

The line graph LG of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix-Tree Theorem to prove a formula…