Lionel Levine

An Algebraic Analogue of a Formula of Knuth
dmtcs:2867 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

https://doi.org/10.46298/dmtcs.2867
An Algebraic Analogue of a Formula of Knuth
Authors: Lionel Levine ^{1}
0000000301056754
Lionel Levine
1 Department of Mathematics [MIT]
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.