2009/10/19 by Hoda Bidkhori, Bidkhori, Hoda, Shaunak Kishore +1
Computer Science · Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #Data Management and Algorithms #FOS: Mathematics #Theoretical and Computational Physics #math.CO
paper · pdf · doi:10.48550/arxiv.0910.3442
14 pages, 3 figures
arxiv created 2009/10/19 · openalex publication_date 2009/10/19 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Knuth's formula. As a result of this proof we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2n-1. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine.