| HAL-Inria | Publications, software ... of Inria's scientists |
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.
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
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