A Combinatorial Proof of the All Minors Matrix Tree Theorem

DOI10.1137/0603033zbMath0495.05018OpenAlexW2087720847MaRDI QIDQ3958479

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

Trees (05C05) Enumeration in graph theory (05C30) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Matroids arising from electrical networks, Moore-Penrose inverse of incidence matrix of graphs with complete and cyclic blocks, On spectra of spectra, The Grassmann-Berezin calculus and theorems of the matrix-tree type, A combinatorial approach to matrix algebra, On coefficients of the characteristic polynomial of the Laplace matrix of a weighted digraph and the all minors theorem, Arborescences of covering graphs, Free energy of $\widehat{D_n}$ quiver Chern-Simons theories, On the relationship between the multiplicities of the matrix spectrum and the signs of the components of its eigenvectors in a tree-like structure, Weighted complexities of graph products and bundles, Hook immanantal inequalities for Laplacians of trees, Balanced vertex weightings and arborescences, Bideterminants, arborescences and extension of the matrix-tree theorem to semirings, Graphical functions in parametric space, On the characteristic polynomial and eigenvectors in terms of the tree-like structure of a digraph, Multivariable Lagrange inversion, Gessel-Viennot cancellation, and the matrix tree theorem, Some methods for counting the spanning trees in labelled molecular graphs, examined in relation to certain fullerenes, Resistance characterizations of equiarboreal graphs, Generalized bicycles, Identifiability of linear compartmental models: the singular locus, A generalized inverse for graphs with absorption, On the determinant of the Laplacian matrix of a complex unit gain graph, Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and Pfaffians, Fully synchronous solutions and the synchronization phase transition for the finite-N Kuramoto model, Exact representation of the asymptotic drift speed and diffusion matrix for a class of velocity-jump processes, A note on the nullity of unicyclic signed graphs, Boundary TBA, trees and loops, Sandpile groups and spanning trees of directed line graphs, Tutte's barycenter method applied to isotopies, The exchange graph and variations of the ratio of the two Symanzik polynomials, Spanning forest polynomials and the transcendental weight of Feynman graphs, On the rank of weighted graphs, Resistance distance and spanning 2-forest matrices of linear 2-trees, Optimal linear estimator of origin-destination flows with redundant data, Structure of minimum-weight directed forests: related forests and convexity inequalities, On the weighted complexity of a regular covering of a graph, On minors of the compound matrix of a Laplacian, On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication, A generalization of the matrix-tree theorem, Principal minors Pfaffian half-tree theorem, Meso-scale obstructions to stability of 1D center manifolds for networks of coupled differential equations with symmetric Jacobian, On the dependence of the existence of the positive steady states on the rate coefficients for deficiency-one mass action systems: single linkage class, A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem., Lewis Carroll and the red hot potato: a graph theoretic approach to a linear algebraic identity, Matrix-tree theorems and discrete path integration, Homogeneous multivariate polynomials with the half-plane property, The number of spanning trees in self-similar graphs, $R$-systems, Polynomials with the half-plane property and matroid theory, Complete monotonicity for inverse powers of some combinatorially defined polynomials, The symbiotic relationship of combinatorics and matrix theory, Renormalization flow for unrooted forests on a triangular lattice, Enumerative combinatorics of simplicial and cell complexes: Kirchhoff and Trent type theorems, A combinatorial expression for the group inverse of symmetric $M$-matrices, Characterizing immutable sandpiles: a first look, A colourful path to matrix-tree theorems, The stochastic weighted complexity of a group covering of a digraph, Identities of Rothe-Abel-Schläfli-Hurwitz-type, Flow polynomials as Feynman amplitudes and their $\alpha$-representation, Hamiltonian cycle enumeration via fermion-zeon convolution, Spanning forests and the golden ratio, Counting trees with random walks, Laplace spectra of orgraphs and their applications, New proofs for Levine's theorems, Identities for minors of the Laplacian, resistance and distance matrices, The number of spanning trees of a family of 2-separable weighted graphs, The weighted complexity and the determinant functions of graphs, Torsion formulas for signed graphs, On the spectra of nonsymmetric Laplacian matrices, A formula for all minors of the adjacency matrix and an application, Directed forests and the constancy of Kemeny's constant, Higher matrix-tree theorems and Bernardi polynomial, A combinatorial proof of the Rayleigh formula for graphs, Pfaffian orientations and perfect matchings of scale-free networks, A principle for converting Lindström-type lemmas to Stembridge-type theorems, with applications to walks, groves, and alternating flows, The enumeration of spanning tree of weighted graphs, Incidence hypergraphs: injectivity, uniformity, and matrix-tree theorems, Epidemiologic network inference, Sequence graphs: characterization and counting of admissible elements, The Tutte polynomial of a ported matroid, Oriented hypergraphic matrix-tree type theorems and bidirected minors via Boolean order ideals, Effective fluctuation and response theory, The combinatorics of effective resistances and resistive inverses, A study on prefixes of $c_2$ invariants, Spanning 2-forests and resistance distance in 2-connected graphs, Spectra of signed graphs, Electrical networks and hyperplane arrangements, Determinant identities for Laplace matrices, A generalization of the all minors matrix tree theorem to semirings, Distance matrix and Laplacian of a tree with attached graphs, On the dissection of rectangles into right-angled isosceles triangles, Extremal spectral results related to spanning trees of signed complete graphs, Bounds for the least Laplacian eigenvalue of a signed graph, Forest matrices around the Laplacian matrix, Matrix-tree theorem of digraphs via signless Laplacians, Some determinant expansions and the matrix-tree theorem, On the Laplacian coefficients of signed graphs, Spectral characterizations of signed lollipop graphs, Variances and covariances in the central limit theorem for the output of a transducer, Laplacian matrices of graphs: A survey, Bicycles and Spanning Trees, Determinant: Old algorithms, new insights, On the Laplacian Eigenvalues of Signed Graphs, Abelian networks IV. Dynamics of nonhalting networks, Kemeny's Constant And An Analogue Of Braess' Paradox For Trees, The Group Inverse of the Laplacian Matrix of a Graph, Tangles and links: A view with trees, Geometrical Characterization of Sensor Placement for Cone-Invariant and Multi-Agent Systems against Undetectable Zero-Dynamics Attacks, Coding and counting spanning trees in Kleitman-Golden graphs, Forest formulas of discrete Green's functions, Sensitivity of Steady States in Networks with Application to Markov Chains and Chemical Reaction Networks, Generating functions and counting formulas for spanning trees and forests in hypergraphs, Generalizing Kirchhoff laws for Signed Graphs, Resistance distance in connected balanced digraphs, Oriented spanning trees and stationary distribution of digraphs, Signed distance Laplacian matrices for signed graphs, Families of graphs with twin pendent paths and the Braess edge, Unnamed Item, Matroids—the Engineers’ Revenge, Unnamed Item, Unnamed Item, An Elementary Proof of a Matrix Tree Theorem for Directed Graphs, The Complexity of Power Graphs Associated With Finite Groups, Incomplete graphical model inference via latent tree aggregation, On the complexity group of stable curves, Schramm’s formula for multiple loop-erased random walks, Generalized matrix tree theorem for mixed graphs, Digraphs with Distinguishable Dynamics Under the Multi‐Agent Agreement Protocol, FEYNMAN GRAPH POLYNOMIALS, A minimax-condition for the characteristic center of a tree, A special case of completion invariance for the $c_2$ invariant of a graph, Vertex Weighted Complexities of Graph Coverings, Resistors in dual networks, On two Laplacian matrices for skew gain graphs, Identities for minors of the Laplacian, resistance and distance matrices of graphs with arbitrary weights, Negative dependence and the geometry of polynomials, Volume Bounds for the Phase-Locking Region in the Kuramoto Model with Asymmetric Coupling, Knot invariants from Laplacian matrices, Relation between the rank of a signed graph and the rank of its underlying graph, Impact of Varying Community Networks on Disease Invasion, Feynman Graphs, Alexander polynomial and spanning trees, Laminations of a graph on a pair of pants, Edge version of the matrix tree theorem for trees, Watermelons on the half-plane, Decoding from Pooled Data: Sharp Information-Theoretic Bounds, Resistance distance in directed cactus graphs

Cites Work