Linear algebraic techniques for weighted spanning tree enumeration

DOI10.1016/J.LAA.2019.08.009zbMATH Open1426.05069arXiv1903.03575OpenAlexW2922387598WikidataQ127358319 ScholiaQ127358319MaRDI QIDQ2332392FDOQ2332392

Steven Klee, Matthew T. Stamps

Publication date: 4 November 2019

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

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.

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

zbMATH Keywords

matrix-tree theoremSchur complementsmatrix determinant lemmaweighted spanning trees

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Threshold graphs and related topics
• Degree maximal graphs are Laplacian integral
• Enumerative properties of Ferrers graphs
• Factorizations of some weighted spanning tree enumerators
• The number of spanning trees of a complete multipartite graph
• Linear algebraic techniques for weighted spanning tree enumeration

Cited In (13)

• Linear algebraic techniques for weighted spanning tree enumeration
• Enumeration of spanning trees of complete multipartite graphs containing a fixed spanning forest
• Counting spanning trees in almost complete multipartite graphs
• A combinatorial expression for the group inverse of symmetric \(M\)-matrices
• Title not available (Why is that?)
• Linear Algebraic Techniques for Spanning Tree Enumeration
• Resistance distances and the Moon-type formula of a vertex-weighted complete split graph
• Determinant identities for Laplace matrices
• Biconed graphs, weighted forests, and \(h\)-vectors of matroid complexes
• Resistance distances in generalized join graphs
• Counting spanning trees with a Kekulé structure in linear hexagonal chains
• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• Spanning tree enumeration and nearly triangular graph Laplacians

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)