### Abstract

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 κ such that whenever φ(u) ≤ κ < φ(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.

Original language | English |
---|---|

Pages (from-to) | 7-15 |

Number of pages | 9 |

Journal | Journal of Graph Theory |

Volume | 31 |

Issue number | 1 |

DOIs | |

Publication status | Published - 1 Jan 1999 |

Externally published | Yes |

### Keywords

- Bipartite labeling
- Graceful tree conjecture