Alternating Extremes in Graceful Labelings of Full Binary Trees and Spider Trees

Bogdan Dumitru; Mihai Nacu

REVIEW 1 major objections 4 minor 13 references

The paper proves that every comb full binary tree admits a graceful labeling whose longest root-to-leaf path carries the alternating extreme labels 0, n−1, 1, n−2, …, and verifies the same pinned-spine conjecture for all rooted non-isomorph

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 06:24 UTC pith:7B2UPKIA

load-bearing objection Solid constructive results in graceful labelings; the math checks out, but the exhaustive order-23 verification is unauditable as submitted. the 1 major comments →

arxiv 2607.12597 v2 pith:7B2UPKIA submitted 2026-07-14 math.CO

Alternating Extremes in Graceful Labelings of Full Binary Trees and Spider Trees

Bogdan Dumitru , Mihai Nacu This is my paper

classification math.CO MSC 05C7805C0505C85

keywords graceful labelingpinned-spine conjecturefull binary treespider treealternating extreme spineself-matched legscomb treealpha-labeling

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper strengthens the usual graceful-labeling question for full binary trees: instead of only asking for a labeling whose edge differences are 1..n−1, it pins a longest root-to-leaf path to carry the alternating extreme sequence 0, n−1, 1, n−2, … . It proves this pinned-spine conjecture for the comb family of full binary trees, and an exhaustive search confirms it for every rooted non-isomorphic full binary tree through 23 vertices, with a one-leaf relaxation through 25. For spider trees it proves a self-matched packing theorem: disjoint arms rooted at hub label 1, at least one containing label 0, combine into a graceful spider once all unused labels are attached as hub leaves. That yields graceful labelings for spiders with prescribed nontrivial arm lengths and sufficiently many unit leaves. A threshold example shows a pinned-spine labeling cannot always be chosen with the extra α-property, so any general proof must handle gapped off-spine label sets.

Core claim

One deepest root-to-leaf path can be pinned to the alternating extremes 0, n−1, 1, n−2, … without destroying gracefulness. Theorem 2.4 proves this for every comb FBT, with leaf edges using exactly the remaining differences 1,…,ℓ; Lemma 2.3 forces off-spine labels into a middle interval and differences into the lower range. For spiders, Theorem 3.3 packs pairwise disjoint self-matched legs rooted at hub 1 (one containing label 0) into a graceful spider with unused labels as hub leaves. The conjecture is verified for all rooted non-isomorphic FBTs through order 23; the six-arm problem reduces to an offset five-arm residual.

What carries the argument

The machinery is the alternating extreme walk: along a path, labels are generated from a starting label by adding a prescribed list of differences with alternating signs. The spine segregation lemma (Lemma 2.3) fixes the residual label and difference sets once the spine is pinned. For spiders, the matching map τ_n (0 ↦ n−1, x ↦ x−1 for x≥2) defines self-matched legs: a leg is self-matched when the differences along it equal τ_n applied to its own labels; Theorem 3.3 packs such legs. Explicit legs are built from arithmetic progressions (multiplicative legs) and from powers of two plus the extremes (closure templates).

Load-bearing premise

The computational verification claim rests on the correctness of the recursive generator of rooted non-isomorphic FBTs and the pinned-spine completion search; an undetected bug or a missed mirror duplicate would invalidate the through-order-23 claim, although the comb and packing theorems have independent proofs.

What would settle it

Run an independent, from-scratch enumeration of rooted non-isomorphic full binary trees of order 23 and a separate exact pinned-spine completion search over every tree, with a second implementation or cross-checked canonical signatures; if any tree lacks a completion, the exhaustive claim collapses.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

Every comb FBT C_ℓ, ℓ≥1, admits a graceful labeling with a prescribed alternating extreme spine that also realizes the remaining small differences on the leaf edges.
The spine segregation lemma gives a necessary profile for any pinned-spine labeling: off-spine vertices use exactly the middle labels and off-spine edges use exactly the differences {1,…,n−ℓ−1}.
The exhaustive search provides concrete finite evidence that the pinned-spine conjecture holds for all rooted non-isomorphic FBTs through order 23.
For spiders, any collection of pairwise label-disjoint self-matched legs rooted at hub 1, with one containing label 0, yields a graceful spider when all leftover labels are attached as hub leaves.
Consequently, the spider family S(c, L_1, …, L_r, 1^t) has graceful labelings for every fixed nontrivial arm profile once t is sufficiently large, and the six-arm problem is reduced to an offset, hub-pinned five-arm residual problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Beyond the paper's claims, the comb proof's monotone pairing—low spine labels get decreasing middle labels, high spine labels get increasing ones—likely extends to any FBT whose side branches can be labeled monotonically, giving a constructive template for the general conjecture.
Beyond the paper's claims, the threshold obstruction indicates that a proof of the pinned-spine conjecture cannot run through α-labelings; any successful strategy must tolerate gapped label sets on side subtrees.
Beyond the paper's claims, the self-matched packing theorem rephrases graceful spider labeling as a set-partition problem: if one could build short self-matched legs without relying on the 'contains 0' condition, the packing method might reach spiders with few leaves.
Beyond the paper's claims, the apparent smallness of the largest-difference-first search suggests a deterministic ordering may hide behind the backtracking; proving that would turn the heuristic into a constructive algorithm.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

Solid constructive results in graceful labelings; the math checks out, but the exhaustive order-23 verification is unauditable as submitted.

read the letter

Bottom line: this is a useful paper with carefully proved constructive results. I checked the main theorems — comb FBTs, the packing theorem, the closure templates, the threshold obstruction — and they hold. The only real weakness is that the much-advertised exhaustive verification through order 23 has no public code or data to back it up.

The genuinely new pieces are Theorem 2.4 (alternating extreme spine labelings for comb FBTs), the segregation lemma that explains why the spine forces a residual middle-block problem, and Theorem 3.3's self-matched packing construction with the explicit leg templates. The six-arm reduction to an offset hub-zero five-arm problem is a well-stated concrete target, and the threshold obstruction (Example 2.5) is a clean counterexample showing pinned-spine α-labelings don't always exist. All of these are solid.

I also like that the paper is honest about what is conditional: the hub-zero five-arm hypothesis and the offset formulation are clearly labeled as open targets. The counts in Table 1 match the Wedderburn–Etherington sequence exactly, which is good evidence the FBT generator is right.

The soft spot is the computational claim. The 'Code availability' paragraph says the programs are in an 'accompanying github repository,' but there's no URL, no commit hash, no test oracle. The enumeration counts matching a known sequence is reassuring, but the completion search could have a bug and still produce the table. As submitted, that particular claim cannot be checked. That's not a flaw in the theorems, but it should be fixed before the paper appears in a journal.

There are also minor presentational things: the strict heuristic and one-leaf relaxation are described at a high level, but they aren't the main result.

Who should read this: anyone working on the Graceful Tree Conjecture or on spider labelings. It gives new infinite families and a crisp residual problem to attack. I'd send it to review; the mathematical content deserves referee time. Ask the authors for the code as part of the revision.

Referee Report

1 major / 4 minor

Summary. The paper studies strengthened graceful labeling problems in which an alternating extreme label sequence is pinned to a distinguished root-to-leaf path (for full binary trees) or to the longest arm / hub (for spider trees). In the FBT part, Conjecture 2.2 asks every full binary tree to have a graceful labeling whose longest root-to-leaf path receives labels 0, n-1, 1, n-2, ... ; the authors prove a segregation lemma (Lemma 2.3), prove the conjecture for comb FBTs (Theorem 2.4), give a threshold obstruction showing that a pinned-spine labeling need not be an alpha-labeling (Example 2.5), and report an exhaustive computation through order 23 (Table 1). In the spider part, the authors introduce self-matched legs and prove a packing theorem (Theorem 3.3) with explicit leg constructions (Theorems 3.4 and 3.5), yielding graceful labelings of leaf-extended spiders (Corollary 3.6). They also give a safe-zone reduction (Lemma 3.1), report LDF search results, and reduce the six-arm problem to an offset five-arm residual problem (Proposition 3.8 and Section 3.5).

Significance. The constructive results are genuine, self-contained additions. The comb-FBT theorem and the self-matched packing theorem provide explicit, checkable label assignments, and the threshold obstruction is a clean example showing that the pinned-spine property is strictly weaker than the existence of a pinned alpha-labeling. The closure and multiplicative leg templates are elementary but useful, and the leaf-extended spider corollary gives a new infinite family of graceful spiders. The exhaustive FBT verification, if reproducible, would be a meaningful data point for Conjecture 2.2. However, the computational claim is currently not auditable: the manuscript announces a GitHub repository but gives no URL, repository name, or commit hash, and no independent verifier for the FBT search is described. This limits the weight that can be placed on the exhaustive-verification claim as submitted.

major comments (1)

[Section 2.5 / Code availability] The central computational claim—that the exact pinned-spine search verified Conjecture 2.2 for all rooted non-isomorphic FBTs through order 23 (Table 1, abstract)—is not reproducible as submitted. The final 'Code availability' paragraph says the C++ programs are in 'the accompanying github repository' but gives no URL, repository name, commit hash, or integrity hash. The FBT search also has no described test oracle or independent verifier (the verifier mentioned in Section 3.4 is only for the LDF spider computations). A bug in the generator or the backtracking completion search would silently produce exactly the kind of table shown. Since this exhaustive verification is part of the paper's advertised contribution, the authors should either provide a stable, versioned artifact with enough detail to reproduce the search, or explicitly downgrade the claim to non-exhaustive computational evi

minor comments (4)

[Theorem 3.5] The prefix notation in the L≥4 closure template, '1,2^{r-1}+1,2^{r-2}+1,...,3,2', is ill-formed for r=1 (when L=4), since the displayed tail '3,2' suggests two terms but the formula yields only '2'. Please state the L=4 case explicitly or adjust the notation so the base case is unambiguous.
[Section 3.5] In the normalization paragraph, the sentence 'Since no internal edge between labels in {1,...,s} has differences' is incomplete. The intended point appears to be that internal edges between labels 1..s cannot realize the difference s, so one hub-edge difference must equal s. Please rephrase.
[Table 1] The column header 'n FBTs tested' is slightly ambiguous. Consider renaming to 'Number of rooted non-isomorphic FBTs' or 'FBT count' for clarity.
[Section 2.5] The one-leaf relaxation that succeeds through order 25 is stated only informally ('allows only the terminal leaf of a local spine to swap with another label assigned to the same local subtree'). If this claim is meant to be part of the paper's contributions, please give a precise definition or move it to future work.

Circularity Check

0 steps flagged

No circularity: constructions and reductions are self-contained; the missing code URL is a reproducibility limitation, not circularity.

full rationale

The derivation chain contains no fitted parameters, no load-bearing self-citations, and no prediction that reduces to its own input. Lemma 2.3 is a counting consequence of fixing the alternating extreme spine; Theorem 2.4 is an explicit label assignment verified by direct difference checks. The computational verification in Section 2.5 fixes the spine and searches for a completion; the resulting table is an independent computation, not a retrodiction of fitted values. The packing framework (Definition 3.2 and Theorem 3.3) is definition-driven: a self-matched leg is defined by the equality between its edge-difference set and tau_n of its label set, so the proof of Theorem 3.3 unpacks that definition together with injectivity of tau_n and the condition that 0 lies in one leg. This is a transparent sufficient condition, not a posited prediction that is then declared derived. The templates in Theorems 3.4 and 3.5 are verified by explicit difference listings and disjointness checks. Proposition 3.8 is explicitly conditional ('If every five-arm spider admits...') and is labeled as a reduction target, not an asserted theorem; the offset formulation likewise states conditional equivalences. No self-citation is load-bearing. The concrete limitations are non-circular: the code-availability note gives no repository URL or commit hash, making the exhaustive search hard to audit, and the strict heuristic fails on one 13-vertex FBT while the exact search succeeds. These affect reproducibility and computational confidence, not the circularity of the mathematical derivations.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

No free parameters are fitted to data. The new constructs (pinned-spine, self-matched legs, offset hub-zero problem) are definitions, not empirical entities. The central theorems rest on standard bijection arguments plus one unverified computational-enumeration assumption for the supporting search claim.

axioms (2)

domain assumption The recursive splitting with canonical rooted signatures correctly enumerates all rooted non-isomorphic FBTs through order 23 without duplicates.
Needed for the exhaustive-verification claim in Section 2.5 and Table 1; the method is described but not formally proved or independently testable from the manuscript.
standard math Elementary bijection and interval-shifting arithmetic is accepted as standard.
Used throughout the proofs of Lemma 2.3, Theorems 2.4 and 3.3, and Proposition 3.8 without further justification.

pith-pipeline@v1.3.0-alltime-deepseek · 9456 in / 15431 out tokens · 145943 ms · 2026-08-02T06:24:24.634760+00:00 · methodology

0 comments

read the original abstract

We study a pinned form of graceful labeling. For full binary trees, we ask whether some deepest root-to-leaf path can carry the alternating extreme pattern $0,n-1,1,n-2,\dots$. Such a spine uses the extreme labels and largest differences, forcing all off-spine vertices and edges to use the middle labels and smaller differences, respectively. We prove this pinned-spine conjecture for comb full binary trees, verify it computationally for all rooted non-isomorphic full binary trees through order $23$, and give an example showing that a pinned-spine labeling cannot always be chosen as an $\alpha$-labeling. For spider trees, we prove a packing theorem for self-matched legs: pairwise disjoint legs based at hub label $1$, at least one of which contains label $0$, can be combined into a graceful spider, with unused labels attached as hub leaves. This yields graceful labelings for mixed-length spiders with sufficiently many leaves. We also report computations using a depth-first search ordered by largest unused differences and formulate the six-arm problem as an offset five-arm residual problem.

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

13 extracted references · 2 linked inside Pith

[1]

R. E. L. Aldred and B. D. McKay. Graceful and harmonious labellings of trees.Bulletin of the Institute of Combinatorics and its Applications, 23:69–72, 1998

1998
[2]

Bahls, S

P. Bahls, S. Lake, and A. Wertheim. Gracefulness of families of spiders.Involve, 3(3):241–247, 2010

2010
[3]

I. Cahit. Are all complete binary trees graceful?American Mathematical Monthly, 83:35–37, 1976

1976
[4]

H. Fang. A computational approach to the graceful tree conjecture. arXiv:1003.3045, 2010

Pith/arXiv arXiv 2010
[5]

Huang, A

C. Huang, A. Kotzig, and A. Rosa. Further results on tree labellings.Utilitas Mathematica, 21:31–48, 1982

1982
[6]

Kanetkar and S

Alka V. Kanetkar and S. S. Sane. Graceful labeling of a family of quasistars with paths in arithmetic progression.Ars Combinatoria, 83:307–320, 2007

2007
[7]

K. M. Koh, D. G. Rogers, and T. Tan. Interlaced trees: a class of graceful trees. InCombi- natorial Mathematics VI, volume 748 ofLecture Notes in Mathematics, pages 65–78, Berlin,
[8]

K. M. Koh, D. G. Rogers, and T. Tan. Another class of graceful trees.Journal of the Australian Mathematical Society. Series A, 31(2):226–235, 1981

1981
[9]

Panpa, S

A. Panpa, S. Imnang, and T. Wasuanankul. Graceful labeling of spider graphs with at most five legs.Journal of Applied Mathematics, 2025(1):1–5, 2025. Article ID 5826777. 12

2025
[10]

Panpa and T

A. Panpa and T. Poomsa-ard. On graceful spider graphs with at most four legs of lengths greater than one.Journal of Applied Mathematics, 2016:1–5, 2016. Article ID 5327026

2016
[11]

A. Rosa. On certain valuations of the vertices of a graph. InTheory of Graphs (Internat. Sympos., Rome, 1966), pages 349–355. Gordon and Breach, 1967

1966
[12]

Graceful labeling of two families of spiders

Songling Shan and Yucheng Zhong. Graceful labeling of two families of spiders. arXiv:2605.14295, 2026

Pith/arXiv arXiv 2026
[13]

R. G. Stanton and C. R. Zarnke. Labellings of balanced trees. InProceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congressus Numerantium, pages 479–495, Winnipeg, 1973. Utilitas Mathematica. 13

1973

[1] [1]

R. E. L. Aldred and B. D. McKay. Graceful and harmonious labellings of trees.Bulletin of the Institute of Combinatorics and its Applications, 23:69–72, 1998

1998

[2] [2]

Bahls, S

P. Bahls, S. Lake, and A. Wertheim. Gracefulness of families of spiders.Involve, 3(3):241–247, 2010

2010

[3] [3]

I. Cahit. Are all complete binary trees graceful?American Mathematical Monthly, 83:35–37, 1976

1976

[4] [4]

H. Fang. A computational approach to the graceful tree conjecture. arXiv:1003.3045, 2010

Pith/arXiv arXiv 2010

[5] [5]

Huang, A

C. Huang, A. Kotzig, and A. Rosa. Further results on tree labellings.Utilitas Mathematica, 21:31–48, 1982

1982

[6] [6]

Kanetkar and S

Alka V. Kanetkar and S. S. Sane. Graceful labeling of a family of quasistars with paths in arithmetic progression.Ars Combinatoria, 83:307–320, 2007

2007

[7] [7]

K. M. Koh, D. G. Rogers, and T. Tan. Interlaced trees: a class of graceful trees. InCombi- natorial Mathematics VI, volume 748 ofLecture Notes in Mathematics, pages 65–78, Berlin,

[8] [8]

K. M. Koh, D. G. Rogers, and T. Tan. Another class of graceful trees.Journal of the Australian Mathematical Society. Series A, 31(2):226–235, 1981

1981

[9] [9]

Panpa, S

A. Panpa, S. Imnang, and T. Wasuanankul. Graceful labeling of spider graphs with at most five legs.Journal of Applied Mathematics, 2025(1):1–5, 2025. Article ID 5826777. 12

2025

[10] [10]

Panpa and T

A. Panpa and T. Poomsa-ard. On graceful spider graphs with at most four legs of lengths greater than one.Journal of Applied Mathematics, 2016:1–5, 2016. Article ID 5327026

2016

[11] [11]

A. Rosa. On certain valuations of the vertices of a graph. InTheory of Graphs (Internat. Sympos., Rome, 1966), pages 349–355. Gordon and Breach, 1967

1966

[12] [12]

Graceful labeling of two families of spiders

Songling Shan and Yucheng Zhong. Graceful labeling of two families of spiders. arXiv:2605.14295, 2026

Pith/arXiv arXiv 2026

[13] [13]

R. G. Stanton and C. R. Zarnke. Labellings of balanced trees. InProceedings of the Fourth Southeastern Conference on Combinatorics, Graph Theory and Computing, volume VIII of Congressus Numerantium, pages 479–495, Winnipeg, 1973. Utilitas Mathematica. 13

1973