Elmar Teufl ; Stephan Wagner - Spanning forests, electrical networks, and a determinant identity

dmtcs:2699 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2699
Spanning forests, electrical networks, and a determinant identity

Authors: Elmar Teufl 1; Stephan Wagner 2

  • 1 Fakultät für Mathematik = Faculty of Mathematics [Bielefeld]
  • 2 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]

We aim to generalize a theorem on the number of rooted spanning forests of a highly symmetric graph to the case of asymmetric graphs. We show that this can be achieved by means of an identity between the minor determinants of a Laplace matrix, for which we provide two different (combinatorial as well as algebraic) proofs in the simplest case. Furthermore, we discuss the connections to electrical networks and the enumeration of spanning trees in sequences of self-similar graphs.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
Keywords: spanning forest,electrical network,Laplace matrix,determinant identity,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

2 Documents citing this article

Consultation statistics

This page has been seen 212 times.
This article's PDF has been downloaded 186 times.