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 ) ≤ (5 n + 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 5 n /7. © 1995 John Wiley & Sons, Inc.