2021/09/12 by Jiang, Rain, Jiang, Kai, Jiang, Minghui
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2109.05630
Let p(m) (respectively, q(m)) be the maximum number k such that any tree with m edges can be transformed by contracting edges (respectively, by removing vertices) into a caterpillar with k edges. We derive closed-form expressions for p(m) and q(m) for all m ≥ 1. The two functions p(n) and q(n) can also be interpreted in terms of alternating paths among n disjoint line segments in the plane, whose 2n endpoints are in convex position.