RESUMEN

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 5n/7  (n)  (5n + 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)  5n/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 5n/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