Double-star labellings of defect one can require arbitrarily many edge-difference changes
For a bijective labelling of an n-vertex tree by 0,...,n-1, define its defect as n-1 minus the number of distinct absolute edge differences. We compare two labellings by counting the fixed edges on which their differences disagree. For every integer s >= 2, we construct a double star on n_s = 16s^3 + 8s^2 + 8s + 2 vertices and a labelling of defect exactly one whose distance from every graceful labelling of that same tree is at least s+1. Thus no finite bound depending only on the defect controls this repair distance, even for double stars. The lower bound is Omega(n_s^(1/3)) along the constructed family; no optimality is claimed. The proof is elementary and covers all graceful target labellings, including both centre orientations and arbitrary vertex relabellings. The trees themselves admit explicit graceful labellings. This result neither proves nor disproves the graceful tree conjecture, and gives no lower bound on vertex relabelling counts or algorithmic running time. Version 1 contains the five-page preprint and its complete editable LaTeX source. OpenAI Codex was used extensively in the construction and derivation of the argument, manuscript preparation, and internal verification, as disclosed in the paper. Internal checking does not constitute independent human review, external peer review, or verification by a formal proof assistant. A targeted literature check does not establish exhaustive coverage or priority.
Authors
- Fangqi Lou (ORCID: https://orcid.org/0009-0007-8925-315X)
Institutions
- University of Electronic Science and Technology of China (CN)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-09-30
- DOI
- https://doi.org/10.5281/zenodo.23045863
- Primary Topic
- Graph Labeling and Dimension Problems
- Type
- preprint