A Stronger Lower Bound on Parametric Minimum Spanning Trees

2021/05/11 by David Eppstein, Eppstein, David
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2105.05371

openalex publication_date 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter λ, the number of different minimum spanning trees obtained as the parameter varies can be Ω(mlog n).

Related

• A note on universal graphs for spanning trees
• The spanning tree spectrum: improved bounds and simple proofs
• Alternative proof of upper bound of spanning trees in a graph
• Successive minimum spanning trees
• Sharp estimates for spanning trees