Spanning trees with few branch vertices
Research output: Contribution to journal › Article › peer-review
Authors
Colleges, School and Institutes
Abstract
A branch vertex in a tree is a vertex of degree at least three. We prove that, for all s ≥ 1, every connected graph on n vertices with minimum degree at least ((1/(s+3)) + o(1))n contains a spanning tree having at most s branch vertices. Asymptotically, this is best possible and solves, in less general form, a problem of Flandrin, Kaiser, Kužel, Li and Ryjáček, which was originally motivated by an optimization problem in the design of optical networks.
Bibliographic note
19 pages
Details
| Original language | English |
|---|---|
| Pages (from-to) | 1503–1520 |
| Number of pages | 18 |
| Journal | SIAM Journal on Discrete Mathematics |
| Volume | 33 |
| Issue number | 3 |
| Publication status | Published - 22 Aug 2019 |
Keywords
- math.CO, cs.DM, regularity, absorbing, robust subgraphs, spanning trees, optical networks