Spanning trees with few branch vertices

2017/09/14 by DeBiasio, Louis, Lo, Allan
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1709.04937

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, Kuuzel, Li and Ryjáucek, which was originally motivated by an optimization problem in the design of optical networks.

Related

• Spanning trees in connected graphs with few branch and end vertices
• Spanning Trees Minimizing Branching Costs
• Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
• Spanning trees without adjacent vertices of degree 2
• Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Asymptotic Result