Linear algebraic techniques for spanning tree enumeration
From MaRDI portal
(Redirected from 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
- Degree maximal graphs are Laplacian integral
- Enumerative properties of Ferrers graphs
- 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?)
- 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
(29)- Determinant identities for Laplace matrices
- Counting spanning trees in the graphs of Kleitman and Golden and a generalization
- Cycles and spanning trees
- An enumerating function for spanning forests with color restrictions
- An analog of matrix tree theorem for signless Laplacians
- Note on the Pfaffian matrix-tree theorem
- Counting trees with random walks
- Spanning trees of descendants of a complete graph
- Spanning tree enumeration and nearly triangular graph Laplacians
- Effective resistances and spanning trees in the complete bipartite graph plus a matching
- Linear algebraic techniques for weighted spanning tree enumeration
- Enumeration of spanning trees of graph: alternative methods
- Biconed graphs, weighted forests, and \(h\)-vectors of matroid complexes
- Counting spanning trees in grid graphs
- Counting spanning trees in cographs: an algorithmic approach
- Counting spanning trees in graphs using modular decomposition
- Kirchhoff's matrix-tree theorem revisited: counting spanning trees with the quantum relative entropy
- scientific article; zbMATH DE number 5532173 (Why is no real title available?)
- The number of spanning trees of a family of plane graph
- Countingk-component forests of a graph
- scientific article; zbMATH DE number 1484041 (Why is no real title available?)
- Spanning trees and hierarchical networks
- An alternate proof of the formula for the characteristic polynomial of a threshold graph
- Yet More Elementary Proof of Matrix-Tree Theorem for Signed Graphs
- Multidimensional Lambert-Euler inversion and vector-multiplicative coalescent processes
- The number of spanning trees in K_n-complement of a bipartite graph
- Around the number of trees in distance-hereditary graphs
- The number of spanning trees of the bipartite complement of a semiregular bipartite graph
- The number of spanning trees in \(K_{m , n}\)-complements of bipartite graphs
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)
