Linear algebraic techniques for weighted spanning tree enumeration

DOI10.1016/J.LAA.2019.08.009MaRDI QIDQ2332392zbMATH OpenOpenAlexWikidataFDO

Authors Steven Klee, Matthew T. Stamps

Publication date 4 November 2019

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.03575

zbMATH Keywords

matrix determinant lemmamatrix-tree theoremSchur complementsweighted spanning trees

Mathematics Subject Classification ID

Trees (05C05) Signed and weighted graphs (05C22) Enumeration in graph theory (05C30) Determinants, permanents, traces, other special matrix functions (15A15)

Abstract: The weighted spanning tree enumerator of a graph $G$ with weighted edges is the sum of the products of edge weights over all the spanning trees in $G$. In the special case that all of the edge weights equal $1$, the weighted spanning tree enumerator counts the number of spanning trees in $G$. The Weighted Matrix-Tree Theorem asserts that the weighted spanning tree enumerator can be calculated from the determinant of a reduced weighted Laplacian matrix of $G$. That determinant, however, is not always easy to compute. In this paper, we show how two well-known results from linear algebra, the Matrix Determinant Lemma and the method of Schur complements, can be used to elegantly compute the weighted spanning tree enumerator for several families of graphs.

Recommendations

• Linear algebraic techniques for spanning tree enumeration
• The enumeration of spanning tree of weighted graphs
• Factorizations of some weighted spanning tree enumerators
• Enumerating spanning trees of graphs with an involution
• Counting Minimum Weight Spanning Trees

Cites work

• Degree maximal graphs are Laplacian integral
• Enumerative properties of Ferrers graphs
• Factorizations of some weighted spanning tree enumerators
• scientific article; zbMATH DE number 2076810 (Why is no real title available?)
• scientific article; zbMATH DE number 6125590 (Why is no real title available?)
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• Linear algebraic techniques for weighted spanning tree enumeration
• The number of spanning trees of a complete multipartite graph
• Threshold graphs and related topics

Cited in

(26)

• Enumerating spanning trees of graphs with an involution
• Applying a combinatorial determinant to count weighted cycle systems in a directed graph
• Determinant identities for Laplace matrices
• Factorizations of some weighted spanning tree enumerators
• The number of spanning trees of a family of 2-separable weighted graphs
• The enumeration of spanning tree of weighted graphs
• Counting spanning trees in almost complete multipartite graphs
• Spanning tree enumeration and nearly triangular graph Laplacians
• A combinatorial expression for the group inverse of symmetric \(M\)-matrices
• Linear algebraic techniques for weighted spanning tree enumeration
• Biconed graphs, weighted forests, and \(h\)-vectors of matroid complexes
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• Linear algebraic techniques for spanning tree enumeration
• Enumeration of spanning trees of middle digraphs
• Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest
• scientific article; zbMATH DE number 7771742 (Why is no real title available?)
• Combinatorial explanation of the weighted Laplacian characteristic polynomial of a graph and applications
• Counting spanning trees with a Kekulé structure in linear hexagonal chains
• Resistance distances and the Moon-type formula of a vertex-weighted complete split graph
• Resistance distances in generalized join graphs
• Around the number of trees in distance-hereditary graphs
• Counting spanning trees with one perfect matching in helicene polygonal chains on the plane and cylinder
• Weighted Moon-type formulae for complete graphs and complete bipartite graphs
• Enumeration of spanning trees containing a perfect matching in linear polygonal chains
• A weighted cellular matrix-tree theorem, with applications to complete colorful and cubical complexes
• Weighted spanning forests with specified roots in complete s-partite graphs

This page was built for publication: Linear algebraic techniques for weighted spanning tree enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2332392)