Bounds on the convex label number of trees (Q1103629)

A convex labelling of a tree is an assignment of distinct non-negative integer labels to vertices such that whenever x, y, and z are the labels of vertices along a path of length 2, then \(y\leq (x+z)/2\). In addition if the tree is rooted, a convex labelling must assign 0 to the root. The convex label number of a tree T is the smallest integer m such that T has a convex labelling with no label greater than m. This paper proves that every rooted tree with n vertices has convex label number \(<4n\), but that for large enough n, there exist n-vertex trees with convex label number \(4n/3+o(n)\) and n-vertex rooted trees with convex label number \(2n+o(n)\).