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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

Double-star labellings of defect one can require arbitrarily many edge-difference changes

Fangqi Lou
Zenodo (CERN European Organization for Nuclear Research)
Graph Labeling and Dimension Problems
preprint

Double-star labellings of defect one can require arbitrarily many edge-difference changes

Fangqi Lou
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
University of Electronic Science and Technology of China (CN)
Graph Labeling and Dimension Problems
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Double-star labellings of defect one can require arbitrarily many edge-difference changes — Fangqi Lou · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS