# 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.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [14 references]

https://hal.inria.fr/hal-01186296
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

### File

dmAN0122.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01186296, version 1

### Citation

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