Mathematics – Combinatorics
Scientific paper
2009-07-27
Mathematics
Combinatorics
Scientific paper
Kirchhoff's matrix-tree theorem states that the number of spanning trees of a graph G is equal to the value of the determinant of the reduced Laplacian of $G$. We outline an efficient bijective proof of this theorem, by studying a canonical finite abelian group attached to $G$ whose order is equal to the value of same matrix determinant. More specifically, we show how one can efficiently compute a bijection between the group elements and the spanning trees of the graph. The main ingredient for computing the bijection is an efficient algorithm for finding the unique $G$-parking function (reduced divisor) in a linear equivalence class defined by a chip-firing game. We also give applications, including a new and completely algebraic algorithm for generating random spanning trees. Other applications include algorithms related to chip-firing games and sandpile group law, as well as certain algorithmic problems about the Riemann-Roch theory on graphs.
No associations
LandOfFree
Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem 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 Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chip-Firing Games, $G$-Parking Functions, and an Efficient Bijective Proof of the Matrix-Tree Theorem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-681035