The Kirchhoff's Matrix-Tree Theorem revisited: counting spanning trees\n with the quantum relative entropy

2011/02/11 by Vittorio Giovannetti, Giovannetti, Vittorio, Simone Severini +1
Computer Science · Mathematics · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Graph theory and applications #Information Theory (cs.IT) #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.1102.2398

openalex publication_date 2011/02/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

By revisiting the Kirchhoff's Matrix-Tree Theorem, we give an exact formula\nfor the number of spanning trees of a graph in terms of the quantum relative\nentropy between the maximally mixed state and another state specifically\nobtained from the graph. We use properties of the quantum relative entropy to\nprove tight bounds for the number of spanning trees in terms of basic\nparameters like degrees and number of vertices.\n

Related

• Determinants, their applications to Markov processes, and a random walk proof of Kirchhoff's matrix tree theorem
• Spectral Determinants of Almost Equilateral Quantum Graphs
• Quantum Verification of Minimum Spanning Tree
• A Beginner's Guide to Counting Spanning Trees in a Graph
• Counting Spanning Trees of Threshold Graphs