Abstract: 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 for the number of spanning trees of LG, and he
asked for a bijective proof. In this paper, we give a bijective proof of a
generating function identity due to Levine which generalizes Knuths
formula. Finally, we determine the critical groups of two families of graphs widely studied in computer science, the Kautz graphs and de Bruijn
graphs. This is a joint work with S. Kishore.