A bijective proof of a theorem of Knuth

DOI10.1017/S0963548310000192MaRDI QIDQ3068810zbMATH OpenOpenAlexWikidataFDO

Authors Hoda Bidkhori, Shaunak Kishore

Publication date 17 January 2011

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.3442

zbMATH Keywords

number of spanning trees

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Graph operations (line graphs, products, etc.) (05C76)

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 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 2^{n-1}. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine.

Recommendations

• An algebraic analogue of a formula of Knuth
• Sandpile groups and spanning trees of directed line graphs
• Bijections in de Bruijn graphs.
• scientific article; zbMATH DE number 841663
• Critical groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields

Cites work

• Chip-firing and the critical group of a graph
• Critical groups for complete multipartite graphs and Cartesian products of complete graphs
• Oriented subtrees of an arc digraph
• The critical group of a threshold graph

Cited in

(14)

• A bijective proof of the q-Saalschütz theorem
• A bijective proof of a Touchard-Riordan formula
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• Distributed bearing vector estimation in multi-agent networks
• Miscellaneous digraph classes
• scientific article; zbMATH DE number 6985711 (Why is no real title available?)
• An algebraic analogue of a formula of Knuth
• Sandpile groups of generalized de Bruijn and Kautz graphs and circulant matrices over finite fields
• scientific article; zbMATH DE number 841663 (Why is no real title available?)
• On Leaf Node Edge Switchings in Spanning Trees of De Bruijn Graphs
• Bijections in de Bruijn graphs.
• A bijective proof and generalization of Siladić's theorem
• Oriented spanning trees and stationary distribution of digraphs
• Subtended angle-based network localization via distributed bearing vector estimation

This page was built for publication: A bijective proof of a theorem of Knuth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3068810)