Abstract matrix-tree theorem

2016/12/12 by Yurii Burman, Burman, Yurii · 1 citation
Computer Science · Mathematics · #05C20 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.1612.03873

openalex publication_date 2016/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The classical matrix-tree theorem discovered by G.Kirchhoff in 1847 relates the principal minor of the nxn Laplace matrix to a particular sum of monomials of matrix elements indexed by directed trees with n vertices and a single sink. In this paper we consider a generalization of this statement: for any k ≥ n we define a degree k polynomial det_n,k of matrix elements and prove that this polynomial applied to the Laplace matrix gives a sum of monomials indexed by acyclic graphs with n vertices and k edges.

Cited by

• Abstract matrix-tree theorem and Bernardi polynomial

Related

• Higher determinants and the matrix-tree theorem
• Around matrix-tree theorem
• An elementary proof of a matrix tree theorem for directed graphs
• A New Matrix-Tree Theorem
• Matrix tree theorem for the net Laplacian matrix of a signed graph