Skip to Main content Skip to Navigation
Conference papers

An Algebraic Analogue of a Formula of Knuth

Abstract : We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph $G$ and its directed line graph $\mathcal{L} G$. The sandpile group is an abelian group associated to a directed graph, whose order is the number of oriented spanning trees rooted at a fixed vertex. In the case when $G$ is regular of degree $k$, we show that the sandpile group of $G$ is isomorphic to the quotient of the sandpile group of $\mathcal{L} G$ by its $k$-torsion subgroup. As a corollary we compute the sandpile groups of two families of graphs widely studied in computer science, the de Bruijn graphs and Kautz graphs.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Monday, August 24, 2015 - 3:48:27 PM
Last modification on : Wednesday, June 26, 2019 - 2:48:03 PM
Long-term archiving on: : Wednesday, November 25, 2015 - 5:52:26 PM


Publisher files allowed on an open archive


  • HAL Id : hal-01186296, version 1



Lionel Levine. An Algebraic Analogue of a Formula of Knuth. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. pp.379-390. ⟨hal-01186296⟩



Record views


Files downloads