Bipartite labeling of trees with maximum degree three

Let T = ( V, E ) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, | V |} for which there exists a k such that whenever φ( u ) ≤ k < φ( v ), then u and v have different colors. The α‐size α( T ) of the tree T is the maximum number of elements in the sets {|φ( u ) − φ( v )|; uv ∈ E }, taken over all bipartite labelings φ of T . The quantity α( n ) is defined as the minimum of α( T ) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5 n /7 ≤ α( n ) ≤ (5 n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of ( n ). In this article, we investigate the α‐size of trees with maximum degree three. Let α 3 ( n ) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α 3 ( n ) ≥ 5 n /6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5 n /6. Using a computer search, we also establish that α 3 ( n ) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999