GRASP Special Seminar – Hoda Bidkhori, North Carolina State University, “The Critical Group of Line Graphs and a Bijective Proof of a Theorem of Knuth”

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.