Combinatorial Identities Using the Matrix Tree Theorem

2025/04/30 by Nayana Shibu Deepthi, Chanchal Kumar, Deepthi, Nayana Shibu +1 · 2 citations
Mathematics · #05C05 #05C30 #05C50 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods

paper · pdf · doi:10.48550/arxiv.2504.21319

openalex publication_date 2025/04/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we explore some interesting applications of the matrix tree theorem. In particular, we present a combinatorial interpretation of a distribution of (n-1)^n-1, in the context of uprooted spanning trees of the complete graph K_n, which was previously obtained by Chauve--Dulucq--Guibert. Additionally, we establish a combinatorial explanation for the distribution of m^n-1n^m-1, related to spanning trees of the complete bipartite graph K_m,n, which seems new. Furthermore, we extend this study to the graph K_n∖ \e_1,n\, obtained by deleting an edge from K_n, and derive a new identity for the number of its uprooted spanning trees.

Cited by

• Eventually constant maps for two sets and nilpotent pairs
• Pairs of eventually constant maps and nilpotent pairs

Related

• A Beginner's Guide to Counting Spanning Trees in a Graph
• Taylor Expansion Proof of the Matrix Tree Theorem - Part I
• Counting Spanning Trees of Threshold Graphs
• A New Matrix-Tree Theorem
• Counting the spanning trees of a directed line graph