Bipartite labelings of trees and the gracesize

Let T = (V, E) be a tree whose vertices are properly 2-colored. A bipartite labeling of T is a bijection f: V ← {0, 1, ?, | E |} for which there is a k such that whenever f(u) ≤ k < f(v), then u and v have different colors. The α-size of the tree T is the maximum number of distinct values of the induced edge labels |f(u) - f(v)|, uv ? E, taken over all bipartite labelings f of T. We investigate the asymptotic behavior of the α-size of trees. Let α(n) be the smallest α-size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 ≤ α(n) ≤ (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is shown to have “gracesize” at least 5n/7. © 1995 John Wiley & Sons, Inc.