BIPARTITE LABELINGS OF TREES AND THE GRACESIZE

Let T=(V, E) be a tree whose vertices are properly 2-colored. A bipart ite labeling of Tis a bijection f: V --> (0, 1,..., \E\) for which the re is a k such that whenever f(u) less than or equal to k < f(v), then u and v have different colors. The alpha-size of the tree Tis the max imum number of distinct values of the induced edge labels \f(u) - f(v) \, uv is an element of E, taken over all bipartite labelings f of T. W e investigate the asymptotic behavior of the alpha-size of trees. Let alpha(n) be the smallest alpha-size among all the trees with n edges. As our main result we prove that 5(n + 1)/7 less than or equal to alph a(n) less than or equal to (5n + 9)/6. A connection with the graceful tree conjecture is established, in that every tree with n edges is sho wn to have ''gracesize'' at least 5n/7. (C) 1995 John Wiley & Sons, In c.