A Bijective Proof of a Theorem of Knuth
| Autor: | Hoda Bidkhori, Shaunak Kishore |
|---|---|
| Rok vydání: | 2010 |
| Předmět: | |
| Zdroj: | Combinatorics, Probability and Computing. 20:11-25 |
| ISSN: | 1469-2163 0963-5483 |
| DOI: | 10.1017/s0963548310000192 |
| Popis: | The line graph G 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 G, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of 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 [7]. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|