Spanning trees with few branch vertices

Research output: Contribution to journalArticlepeer-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 languageEnglish
Pages (from-to)1503–1520
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume33
Issue number3
Publication statusPublished - 22 Aug 2019

Keywords

  • math.CO, cs.DM, regularity, absorbing, robust subgraphs, spanning trees, optical networks