Linear algebraic techniques for spanning tree enumeration
From MaRDI portal
Publication:4960434
Abstract: Kirchhoff's Matrix-Tree Theorem asserts that the number of spanning trees in a finite graph can be computed from the determinant of any of its reduced Laplacian matrices. In many cases, even for well-studied families of graphs, this can be computationally or algebraically taxing. We show how two well-known results from linear algebra, the Matrix Determinant Lemma and the Schur complement, can be used to elegantly count the spanning trees in several significant families of graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 4142059 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 6125590 (Why is no real title available?)
- scientific article; zbMATH DE number 3409376 (Why is no real title available?)
- scientific article; zbMATH DE number 3198646 (Why is no real title available?)
- Degree maximal graphs are Laplacian integral
- Enumerative properties of Ferrers graphs
- Laplacian spectra and spanning trees of threshold graphs
- Linear algebraic techniques for weighted spanning tree enumeration
- Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
- The Enumeration of Point Labelled Chromatic Graphs and Trees
- The number of spanning trees of a complete multipartite graph
- Threshold graphs and related topics
Cited in
(25)- Linear algebraic techniques for weighted spanning tree enumeration
- scientific article; zbMATH DE number 1484041 (Why is no real title available?)
- Enumeration of spanning trees of graph: alternative methods
- Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes
- Counting trees with random walks
- An analog of matrix tree theorem for signless Laplacians
- scientific article; zbMATH DE number 5532173 (Why is no real title available?)
- Countingk-component forests of a graph
- Spanning trees of descendants of a complete graph
- Spanning trees and hierarchical networks
- The number of spanning trees in \(K_n\)-complement of a bipartite graph
- Note on the Pfaffian matrix-tree theorem
- An alternate proof of the formula for the characteristic polynomial of a threshold graph
- Determinant identities for Laplace matrices
- Kirchhoff's matrix-tree theorem revisited: counting spanning trees with the quantum relative entropy
- Counting spanning trees in the graphs of Kleitman and Golden and a generalization
- Biconed graphs, weighted forests, and \(h\)-vectors of matroid complexes
- Effective resistances and spanning trees in the complete bipartite graph plus a matching
- Yet More Elementary Proof of Matrix-Tree Theorem for Signed Graphs
- An enumerating function for spanning forests with color restrictions
- The number of spanning trees of a family of plane graph
- Counting spanning trees in cographs: an algorithmic approach
- Counting spanning trees in graphs using modular decomposition
- Counting spanning trees in grid graphs
- Spanning tree enumeration and nearly triangular graph Laplacians
This page was built for publication: Linear algebraic techniques for spanning tree enumeration
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960434)
