A tight bound on the collection of edges in MSTs of induced subgraphs
| dc.creator | Sorkin, Gregory B. | |
| dc.creator | Steger, Angelika | |
| dc.creator | Zenklusen, Rico | |
| dc.date | 2007-05-16 | |
| dc.date.accessioned | 2026-07-07T08:01:58Z | |
| dc.date.available | 2026-07-07T08:01:58Z | |
| dc.description | Let $G=(V,E)$ be a complete $n$-vertex graph with distinct positive edge weights. We prove that for $k\in\{1,2,...,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 $nk-\binom{k+1}{2}$ 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. | |
| dc.identifier | https://arxiv.org/abs/0705.2439 | |
| dc.identifier | http://arxiv.org/abs/0705.2439 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/129084 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C40; 05C05 | |
| dc.title | A tight bound on the collection of edges in MSTs of induced subgraphs | |
| dc.type | text |