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

Bogdan Dumitru; Mihai Nacu

Comb full binary trees admit graceful labelings with a pinned alternating extreme spine, and self-matched spider legs pack at hub 1 into graceful spiders.

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 · grok-4.5

2026-07-15 04:50 UTC pith:7B2UPKIA

load-bearing objection Abstract-only existence claims on pinned-spine graceful labelings for combs and a spider packing theorem; real but narrow progress, unauditable without proofs. the 3 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 05C7805C05

keywords graceful labelingfull binary treesspider treespinned spineself-matched legsα-labelingtree packing

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 studies a pinned form of graceful labeling in which a deepest root-to-leaf path is forced to carry the alternating extreme labels 0, n−1, 1, n−2, and so on. It proves that every comb full binary tree has such a pinned-spine graceful labeling, and verifies the claim by computer for every rooted non-isomorphic full binary tree through order 23. An explicit example shows that a pinned-spine labeling cannot always be chosen to be an α-labeling. For spider trees the authors prove a packing theorem: pairwise disjoint self-matched legs based at hub label 1, at least one of which contains label 0, can be combined into a graceful spider by attaching the unused labels as leaves at the hub. The construction yields graceful labelings for mixed-length spiders that possess sufficiently many leaves, and the six-arm problem is reformulated as an offset five-arm residual problem.

Core claim

Every comb full binary tree admits a graceful labeling in which some deepest root-to-leaf path receives the alternating extreme pattern 0, n−1, 1, n−2, …; and any collection of pairwise disjoint self-matched legs based at hub label 1 (at least one containing 0) packs into a graceful spider by attaching the remaining labels as hub leaves.

What carries the argument

The pinned spine—a deepest root-to-leaf path forced to carry the alternating extreme labels 0, n−1, 1, n−2, …—which reserves middle labels and smaller differences for all off-spine edges; together with the packing of self-matched legs at hub label 1 for spiders.

Load-bearing premise

That the enumeration of all rooted non-isomorphic full binary trees through order 23 is complete and that the depth-first search ordered by largest unused differences correctly decides the existence of a pinned-spine graceful labeling for each of them.

What would settle it

Produce a comb full binary tree that admits no graceful labeling whose deepest root-to-leaf path carries the alternating extreme pattern 0, n−1, 1, n−2, …, or produce a set of pairwise disjoint self-matched legs based at hub 1 (one containing 0) that cannot be completed to a graceful spider by hub leaves.

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

If this is right

Every comb full binary tree is graceful with an explicitly pinned alternating spine.
Mixed-length spiders that have enough leaves admit graceful labelings via the self-matched packing construction.
A pinned-spine graceful labeling of a full binary tree need not be an α-labeling.
The six-arm spider problem reduces to an offset five-arm residual problem solvable by the same packing methods.

Where Pith is reading between the lines

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

Successful verification through order 23 suggests the pinned-spine property may hold for all full binary trees and invites a general combinatorial proof.
The same packing idea may extend to other fixed hub labels or to broader classes of caterpillars.
Depth-first search ordered by largest unused differences is a practical heuristic for searching graceful labelings of trees more generally.

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

Abstract-only existence claims on pinned-spine graceful labelings for combs and a spider packing theorem; real but narrow progress, unauditable without proofs.

read the letter

The one thing to know is that this is pure existence work inside the classical graceful-labeling program: they claim a pinned-spine graceful labeling (alternating extremes 0, n−1, 1, n−2, … on a deepest root-to-leaf path) for every comb full binary tree, plus a packing theorem that turns pairwise-disjoint self-matched spider legs based at hub label 1 into a graceful spider with leftover labels as hub leaves. That packing immediately gives graceful labelings for mixed-length spiders that have enough leaves. They also report exhaustive computational checks through order 23 and a counter-example showing pinned-spine need not be an α-labeling.

What is actually new is the pinned-spine formulation itself and the self-matched packing statement. Both sit squarely inside the long-running graceful-tree conjecture rather than inventing a new framework, but they are concrete existence theorems for restricted families that people in the area care about. The comb proof and the packing argument, if they hold, are honest incremental progress; the computational sweep and the α-labeling negative example are useful bookkeeping.

The soft spot is structural and large: we only have the abstract. No proof sketch, no inductive step, no certificate for the order-23 enumeration, no code, no isomorphism filter. The stress-test note is right that the load-bearing material is simply missing, so soundness cannot be audited. That is not a flaw inside a visible argument; it is the absence of the argument. The claims themselves look internally consistent and free of circular fitting, which is normal for this style of combinatorics.

This paper is for people who already work on graceful labelings of trees, especially spiders and binary trees. A general combinatorics reader will not get much. It deserves a serious referee once the full text is available—existence theorems of this type are exactly what referees in math.CO are for—but on abstract alone I would not send it out. Bring it to reading group only if someone is already deep in graceful trees; otherwise skip. I would not cite it yet.

Referee Report

3 major / 3 minor

Summary. The manuscript studies a pinned form of graceful labeling. For full binary trees it asks whether some deepest root-to-leaf path can carry the alternating extreme pattern 0, n−1, 1, n−2, … (a “pinned spine”). It asserts a proof of this property for comb full binary trees, computational verification for all rooted non-isomorphic full binary trees through order 23, and an example showing that a pinned-spine labeling need not be an α-labeling. For spider trees it asserts a packing theorem: pairwise disjoint self-matched legs based at hub label 1, at least one containing 0, can be combined into a graceful spider with unused labels attached as hub leaves, yielding graceful labelings for mixed-length spiders with sufficiently many leaves. Computations via depth-first search ordered by largest unused differences are reported, and the six-arm problem is formulated as an offset five-arm residual.

Significance. Graceful labeling of trees remains a central open problem in combinatorial graph theory. Existence results for infinite families under additional structural constraints (pinned spines on full binary trees; packing of self-matched legs on spiders) would be genuine progress if the arguments hold. The separation of pinned-spine labelings from α-labelings, the computational survey through order 23, and the residual formulation of the six-arm problem are potentially useful contributions. Constructive or machine-checkable proofs and reproducible enumeration would further raise the value of the work.

major comments (3)

[Abstract (comb full binary trees)] The central existence claim for comb full binary trees is asserted in the abstract with no accessible proof sketch, inductive step, constructive description, or parity/height hypotheses. With only the abstract available, the load-bearing argument cannot be audited for completeness or hidden restrictions, so the claim cannot currently be certified.
[Abstract (computational verification through order 23)] Verification for all rooted non-isomorphic full binary trees through order 23 is reported, but no enumeration certificate, isomorphism filter, search-trace, or code is supplied. Completeness of the DFS ordered by largest unused differences is therefore not independently checkable and cannot yet support the empirical pillar of the paper.
[Abstract (spider packing theorem / six-arm residual)] The packing theorem for pairwise disjoint self-matched legs (hub label 1, at least one leg containing 0) is stated as proved, yet no precise statement of hypotheses, outline of the combination argument, or justification of the six-arm residual reduction is available for inspection. The claim is load-bearing for the spider results and remains unauditable from the abstract alone.

minor comments (3)

[Abstract] The terms “pinned-spine graceful labeling” and “self-matched legs” are introduced without formal definitions; the full manuscript should place unambiguous definitions early.
[Abstract] “Comb full binary trees” should be defined or referenced for readers outside the immediate subfield.
[Abstract (counter-example)] The claim that a pinned-spine labeling cannot always be chosen as an α-labeling is useful; the counter-example should be exhibited explicitly with vertex labels.

Circularity Check

0 steps flagged

No significant circularity: pure existence claims in graceful labeling with no fitted parameters, self-definitions, or load-bearing self-citations visible.

full rationale

The abstract presents pure combinatorial existence results (pinned-spine graceful labelings for comb full binary trees; packing of pairwise-disjoint self-matched legs into a graceful spider) together with a finite computational verification through order 23 and an example separating pinned-spine from α-labelings. No parameters are fitted to data and then re-presented as predictions; no quantity is defined in terms of the claim it is said to derive; no uniqueness theorem or ansatz is imported from prior work by the same authors; and the standard definition of graceful labeling is used without renaming a known empirical pattern. Because only the abstract is supplied, the internal steps of the proofs cannot be inspected, yet nothing in the stated claims exhibits a reduction of a “prediction” or “first-principles result” to its own inputs by construction. Residual dependence on the classical definition of graceful labeling is ordinary mathematical practice, not circularity. Score 0 is therefore the correct assessment under the given rules.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 2 invented entities

Pure combinatorial existence paper. Free parameters are absent; the work rests on the standard definition of graceful labeling and ordinary tree terminology. ‘Pinned-spine’ and ‘self-matched legs’ are definitional constructs introduced to state the theorems, not physical entities. No fitted constants appear.

axioms (3)

domain assumption A tree with n edges is graceful if its vertices can be injected into {0,…,n} so that the absolute edge differences are exactly {1,…,n}.
Standard definition of graceful labeling; the entire paper is existence work relative to this definition.
domain assumption Full binary trees and spider trees (hub plus path legs) are the families under study; comb full binary trees form a distinguished subclass.
Structural restrictions that delimit the theorems; ordinary graph-theoretic notions.
domain assumption An α-labeling is a graceful labeling with the additional bipartition property that all edges run between the two color classes with labels below/above a threshold.
Used only for the negative example that pinned-spine need not be α; standard in the literature.

invented entities (2)

pinned-spine graceful labeling (alternating extremes on a deepest root-to-leaf path) no independent evidence
purpose: Restricts graceful labelings of full binary trees so that a deepest path carries 0,n−1,1,n−2,…, forcing middle labels off-spine.
Definitional constraint introduced to state the conjecture and the comb theorem; independent evidence is the computational check through order 23 and the comb proof (both only claimed, not exhibited here).
self-matched legs (for spiders) no independent evidence
purpose: Pre-labeled path legs based at hub label 1 that can be packed when pairwise label-disjoint and at least one contains 0.
Technical device for the packing theorem; existence of such legs is part of the hypothesis of the theorem rather than an external prediction.

pith-pipeline@v1.1.0-grok45 · 6098 in / 2569 out tokens · 30190 ms · 2026-07-15T04:50:47.271501+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.

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

Core claim

What carries the argument

Load-bearing premise

What would settle it

If this is right

Where Pith is reading between the lines

discussion (0)