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

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

File

dmAN0122.pdf
Publisher files allowed on an open archive

Identifiers

Collections

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

Share

Metrics

Record views

55

Files downloads

504