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.

Presenter's biography

Hoda Bidkhori received the B.S. degree in Applied Mathematics Department from Sharif University of Technology, Tehran, Iran, in 2004, and the Ph.D. degree in  Applied Mathematics from the Massachusetts Institute of Technology, Cambridge, in 2010. Since 2010, she has been  a postdoctoral research associate in Applied Mathematics and Statistics Department at North Carolina State University. Hoda Bidkhori is the recipient of the Rogers Family prize at MIT as well as several Medals in International Math Competitions.


Levine 307
3330 Walnut Street
Philadelphia, PA 19104
United States


Hoda Bidkhori