HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
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




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, ⟨10.46298/dmtcs.2867⟩. ⟨hal-01186296⟩



Record views


Files downloads