Graceful supertrees with at most 2m−diam(T) edges
Abstract
A graceful labeling of a tree with m edges is a bijection from its vertices to {0,1,…,m} whose edge differences are pairwise distinct. The Graceful Tree Conjecture asserts that every tree admits such a labeling; equivalently, the smallest graceful tree containing a given m-edge tree has m edges. For this embedding problem, Sethuraman, Ragukumar and Slater proved that fewer than 4m edges suffice, while Sethuraman and Ragukumar observed that in practice fewer than 2m appear to suffice. We prove the latter bound for every tree. For any root of height h with th vertices at maximum distance, we construct a graceful tree containing the original tree with exactly M=2m−h−th+1 edges; in particular, 2m−diam(T) edges suffice. The construction completes a cyclic reflection of van Bussel's level labeling without increasing its span; each original edge difference d is replaced by M+1−d. Unused vertex labels and missing edge differences are indexed by the same intermediate-level positions, allowing an explicit attachment rule that preserves the tree property. The best root for this construction is computable in linear time. Because every graceful supertree labeling restricts to a range-relaxed labeling, a uniform supertree bound of (2−ε)m+O(1) would imply such a range-relaxed bound for all trees.
Related
- Rainbow maps and the number of graceful labelings of trees
- Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
- Strongly separating graph edges with 10n paths
- Band edges of periodic Schrödinger operators are generically isolated and nondegenerate
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
BibTeX
@misc{okechukwu2026graceful,
title = {{Graceful supertrees with at most $2m-\mathrmdiam(T)$ edges}},
author = {Obinna Okechukwu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01340},
eprint = {2611.01340},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01340},
}
RIS
TY - UNPB
TI - Graceful supertrees with at most 2m−diam(T) edges
AU - Obinna Okechukwu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01340
UR - https://arxiv.org/abs/2611.01340
AB - A graceful labeling of a tree with m edges is a bijection from its vertices to {0,1,…,m} whose edge differences are pairwise distinct. The Graceful Tree Conjecture asserts that every tree admits such a labeling; equivalently, the smallest graceful tree containing a given m-edge tree has m edges. For this embedding problem, Sethuraman, Ragukumar and Slater proved that fewer than 4m edges suffice, while Sethuraman and Ragukumar observed that in practice fewer than 2m appear to suffice. We prove the latter bound for every tree. For any root of height h with t_h vertices at maximum distance, we construct a graceful tree containing the original tree with exactly M=2m−h−t_h+1 edges; in particular, 2m−diam(T) edges suffice. The construction completes a cyclic reflection of van Bussel's level labeling without increasing its span; each original edge difference d is replaced by M+1−d. Unused vertex labels and missing edge differences are indexed by the same intermediate-level positions, allowing an explicit attachment rule that preserves the tree property. The best root for this construction is computable in linear time. Because every graceful supertree labeling restricts to a range-relaxed labeling, a uniform supertree bound of (2−ε)m+O(1) would imply such a range-relaxed bound for all trees.
ER -