×

A tight bound on the collection of edges in MSTs of induced subgraphs. (English) Zbl 1229.05156

Summary: Let \(G=(V,E)\) be a complete \(n\)-vertex graph with distinct positive edge weights. We prove that for \(k\in \{1,2,\ldots ,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 Vondrák [M. X. Goemans and J. Vondrák, “Covering minimum spanning trees of random subgraphs”, Random Struct. Algorithms 29, No. 3, 257–276 (2006; Zbl 1108.05082)]. 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.

MSC:

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

Citations:

Zbl 1108.05082
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Goemans, M. X.; Vondrák, J., Covering minimum spanning trees of random subgraphs, Random Structures Algorithms, 29, 3, 257-276 (2005) · Zbl 1108.05082
[2] Halin, R., Zur Theorie der \(n\)-fach zusammenhängenden Graphen, Abh. Math. Sem. Univ. Hamburg, 33, 133-164 (March 1969)
[3] Mader, W., Minimale \(n\)-fach zusammenhängende Graphen, J. Reine Angew. Math., 249, 201-207 (1971) · Zbl 0214.51502
[4] Mader, W., Ecken vom Grad \(n\) in minimalen \(n\)-fach zusammenhängenden Graphen, Arch. Math., 23, 219-224 (1972) · Zbl 0212.29402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.