A Combinatorial Proof of the All Minors Matrix Tree Theorem

DOI10.1137/0603033zbMath0495.05018MaRDI QIDQ3958479

Seth Chaiken

Publication date: 1982

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0603033

zbMATH Keywords

signed graphs; forests; spanning trees

Mathematics Subject Classification ID

05C05: Trees

05C30: Enumeration in graph theory

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Related Items

Edge version of the matrix tree theorem for trees, On the Laplacian Eigenvalues of Signed Graphs, A minimax-condition for the characteristic center of a tree, Weighted complexities of graph products and bundles, The stochastic weighted complexity of a group covering of a digraph, A combinatorial proof of the Rayleigh formula for graphs, A combinatorial approach to matrix algebra, Balanced vertex weightings and arborescences, A generalization of the matrix-tree theorem, The symbiotic relationship of combinatorics and matrix theory, Identities of Rothe-Abel-Schläfli-Hurwitz-type, The combinatorics of effective resistances and resistive inverses, A generalization of the all minors matrix tree theorem to semirings, Some determinant expansions and the matrix-tree theorem, Laplacian matrices of graphs: A survey, Hook immanantal inequalities for Laplacians of trees, Bideterminants, arborescences and extension of the matrix-tree theorem to semirings, Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem, Generalized bicycles, Tutte's barycenter method applied to isotopies, On the weighted complexity of a regular covering of a graph, A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem., Homogeneous multivariate polynomials with the half-plane property, On the spectra of nonsymmetric Laplacian matrices, The Tutte polynomial of a ported matroid, On the dissection of rectangles into right-angled isosceles triangles, Forest matrices around the Laplacian matrix, The Grassmann-Berezin calculus and theorems of the matrix-tree type, Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes, Polynomials with the half-plane property and matroid theory, Renormalization flow for unrooted forests on a triangular lattice, Spanning forests and the golden ratio, Laplace spectra of orgraphs and their applications, Distance matrix and Laplacian of a tree with attached graphs, Bounds for the least Laplacian eigenvalue of a signed graph, Bicycles and Spanning Trees, Generalized matrix tree theorem for mixed graphs, Coding and counting spanning trees in Kleitman-Golden graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Signed graphs
• Orientation of signed graphs
• Line-digraphs, arborescences and theorems of Tutte and Knuth
• Bimatroids and invariants
• Voltage graphs
• Applications of Menger's graph theorem
• Gammoids and transversal matroids
• On the notion of balance of a signed graph
• Some Generalizations of the Problem of Distinct Representatives
• Matrix Generalizations of Some Theorems on Trees, Cycles and Cocycles in Graphs
• On a Class of Matroids Arising From Paths in Graphs
• On the Vector Representations of Induced Matroids