Spanning trees with few branch vertices
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
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.
|Number of pages||18|
|Journal||SIAM Journal on Discrete Mathematics|
|Publication status||Published - 22 Aug 2019|
- math.CO, cs.DM, regularity, absorbing, robust subgraphs, spanning trees, optical networks