Sandpile groups and spanning trees of directed line graphs

Details Sandpile groups and spanning trees of directed line graphs Sandpile groups and spanning trees of directed line graphs

2009-06-15

arxiv.org/abs/0906.2809v2

Mathematics

Combinatorics

v2 has an expanded section on deletion/contraction for directed graphs, and a more detailed proof of Theorem 2.3. To appear in

Scientific paper

10.1016/j.jcta.2010.04.001

We generalize a theorem of Knuth relating the oriented spanning trees of a directed graph G and its directed line graph LG. 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 LG 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.

Affiliated with

Also associated with

No associations

Rating

Sandpile groups and spanning trees of directed line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sandpile groups and spanning trees of directed line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sandpile groups and spanning trees of directed line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-475116