Linear algebraic techniques for spanning tree enumeration
From MaRDI portal
Publication:4960434
DOI10.1080/00029890.2020.1708171zbMATH Open1437.05106arXiv1903.04973OpenAlexW3104523297MaRDI QIDQ4960434FDOQ4960434
Authors: Steven Klee, Matthew T. Stamps 
Publication date: 16 April 2020
Published in: The American Mathematical Monthly (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1903.04973
Recommendations
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Enumeration in graph theory (05C30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Threshold graphs and related topics
- Title not available (Why is that?)
- Degree maximal graphs are Laplacian integral
- Title not available (Why is that?)
- The Enumeration of Point Labelled Chromatic Graphs and Trees
- Enumerative properties of Ferrers graphs
- Laplacian spectra and spanning trees of threshold graphs
- The number of spanning trees of a complete multipartite graph
- Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
- Linear algebraic techniques for weighted spanning tree enumeration
- Title not available (Why is that?)
Cited In (25)
- Title not available (Why is that?)
- Linear algebraic techniques for weighted spanning tree enumeration
- 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
- Title not available (Why is that?)
- Countingk-component forests of a graph
- Spanning trees and hierarchical networks
- Spanning trees of descendants of a complete graph
- The number of spanning trees in \(K_n\)-complement of a bipartite graph
- An alternate proof of the formula for the characteristic polynomial of a threshold graph
- Note on the Pfaffian matrix-tree theorem
- Kirchhoff's matrix-tree theorem revisited: counting spanning trees with the quantum relative entropy
- Determinant identities for Laplace matrices
- Biconed graphs, weighted forests, and \(h\)-vectors of matroid complexes
- Counting spanning trees in the graphs of Kleitman and Golden and a generalization
- 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)
