Maximum number of spanning trees and connectivity: Graphs with a fixed minimum degree and bipartite graphs

2025/12/13 by Xu, Shaohan, Xu, Kexiang, Damnjanović, Ivan
#05C05 #05C30 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2512.12308

Abstract

The number of spanning trees in a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper we characterize the unique graph with a prescribed vertex (resp. edge) connectivity, minimum degree and order that attains the maximum number of spanning trees. Moreover, all the bipartite graphs are determined with a given vertex (resp. edge) connectivity and order maximizing the number of spanning trees.

Citations

• Spanning Tree Bounds for Grid Graphs
• Algebraic Aspects of Abelian Sandpile Models

Related

• The number of bounded-degree spanning trees
• Maximizing spectral radius and number of spanning trees in bipartite graphs
• The generalized connectivity of complete bipartite graphs
• On the number of spanning trees in bipartite graphs
• Sharp estimates for spanning trees