Bounds on the convex label number of trees

Abstract

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 on a path of length 2 then y≦(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. We prove that every rooted tree (and hence every tree) with n vertices has convex label number less than 4 n. We also exhibit n-vertex trees with convex label number 4 n/3+o(n), and n-vertex rooted trees with convex label number 2 n +o(n). © 1987 Akadémiai Kiadó.