Bipartite labeling of trees with maximum degree three

✍ Scribed by Bonnington, C. Paul; ?ir�?, Jozef

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 258 KB
• Volume: 31
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199905)31:1<7::aid-jgt2>3.0.co;2-y

✦ Synopsis

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.