A tight bound on the collection of edges in MSTs of induced subgraphs

DOI10.1016/J.JCTB.2008.08.008MaRDI QIDQ1003845zbMATH OpenOpenAlexFDO

Authors Gregory B. Sorkin, Angelika Steger, Rico Zenklusen

Publication date 4 March 2009

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.2439, http://www.elsevier.com/wps/find/journaldescription.cws_home/622863/authorinstructions

zbMATH Keywords

Mader's theoremMenger's theoremminimal \(k\)-connected graphminimum spanning treeMSTvertex connectivity

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: Let $G=(V,E)$ be a complete $n$-vertex graph with distinct positive edge weights. We prove that for $kin1,2,\mathrm{...},n-1$, the set consisting of the edges of all minimum spanning trees (MSTs) over induced subgraphs of $G$ with $n-k+1$ vertices has at most $$ elements. This proves a conjecture of Goemans and Vondrak cite{GV2005}. We also show that the result is a generalization of Mader's Theorem, which bounds the number of edges in any edge-minimal $k$-connected graph.

Recommendations

• Successive minimum spanning trees
• Tail bound for the minimal spanning tree of a complete graph.
• On average edge length of minimum spanning trees
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs

Cites work

• Covering minimum spanning trees of random subgraphs
• Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen
• Minimale n-fach zusammenhängende Graphen mit maximaler Kantenzahl.
• Zur Theorie der n-fach zusammenhängenden Graphen

Cited in

(2)

• Bulk-robust combinatorial optimization
• On family of graphs with minimum number of spanning trees

This page was built for publication: A tight bound on the collection of edges in MSTs of induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1003845)