Bipartite labelings of trees and the gracesize
Alexander Rosa, Jozef Širáň · Journal of Graph Theory · 1995
Abstract 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.