Edge version of the matrix tree theorem for trees

DOI10.1080/03081080008818646MaRDI QIDQ4498328zbMATH OpenOpenAlexFDO

Authors Jerrold W. Grossman, R. B. Bapat, Devadatta M. Kulkarni

Publication date 15 August 2000

Published in Linear and Multilinear Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03081080008818646

zbMATH Keywords

Laplacian matrixmatrix tree theoremminorssystem of distinct representations

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15)

Review text

Let \(K= Q^tQ\) where \(Q\) denotes the vertex-edge incidence matrix of a mixed tree \(T\) (which may contain some directed edges). The authors show that a square submatrix of \(K\) has a nonzero determinant if and only if the forests obtained by deleting from \(T\) the edge sets corresponding to the missing rows or the missing columns of the submatrix have a common SDR (that is, if there exists a set of vertices containing exactly one vertex from each component of the two forests). Furthermore, if this is the case, they show that the value of the determinant is, up to sign, the number of common SDR's and they give a combinatorial expression for the sign.

Recommendations

• scientific article; zbMATH DE number 825150
• Generalized matrix tree theorem for mixed graphs
• Yet More Elementary Proof of Matrix-Tree Theorem for Signed Graphs
• scientific article; zbMATH DE number 1538963
• Principal minor version of matrix-tree theorem for mixed graphs

Cites work

• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• An edge version of the matrix-tree theorem and the wiener index
• An enumerating function for spanning forests with color restrictions
• Generalized matrix tree theorem for mixed graphs
• Moore-penrose inverse of the incidence matrix of a tree
• On the adjoint of a matrix associated with trees

Cited in

(15)

• First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph
• On spectral integral variations of mixed graphs
• Singularity of Hermitian (quasi-)Laplacian matrix of mixed graphs
• Largest eigenvalue of a unicyclic mixed graphs
• The Laplacian eigenvalues of mixed graphs
• First eigenvalue of nonsingular mixed graphs with given number of pendant vertices
• Nonsingular mixed graphs with few eigenvalues greater than two
• On eigenvectors of mixed graphs with exactly one nonsingular cycle
• Generalized matrix tree theorem for mixed graphs
• On the least eigenvalue of a unicyclic mixed graph
• scientific article; zbMATH DE number 825150 (Why is no real title available?)
• scientific article; zbMATH DE number 7274714 (Why is no real title available?)
• On weighted directed graphs
• The Laplacian spectrum of a mixed graph
• On edge singularity and eigenvectors of mixed graphs

This page was built for publication: Edge version of the matrix tree theorem for trees

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