pith. sign in

arxiv: 2605.14295 · v2 · pith:KWRKIDHJnew · submitted 2026-05-14 · 🧮 math.CO

Graceful Labeling of Two Families of Spiders

Songling Shan , Yucheng Zhong This is my paper

Pith reviewed 2026-05-19 16:52 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C78
keywords graceful labelingspider graphsGraceful Tree Conjecturetreesgraph labeling
0
0 comments X

The pith

A relaxed joining condition for graceful graphs shows that spiders with legs whose lengths increase at least by a factor of two plus a constant are graceful.

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

The paper establishes a new theorem that lets one attach a path Pn to a vertex u in a gracefully labeled graph G whenever the label of u satisfies a bound f(u) + floor(n/2) + 1 ≤ n and n is not congruent to 1 mod 4, producing a new graceful graph. This relaxed attachment rule is then applied to families of spider trees, proving that any spider whose legs satisfy |E(L2)| ≥ 2|E(L1)| + 4 and each later leg at least twice the previous plus two edges is graceful. The authors also supply an explicit graceful labeling for the family of spiders that have one leg of arbitrary length and all remaining legs of length at most two, with the center vertex labeled zero; this labeling can be used to build still larger graceful spiders by further attachments at the center.

Core claim

If G admits a graceful labeling f in which some vertex u satisfies f(u) + floor(n/2) + 1 ≤ n and n ≢ 1 (mod 4), then the graph formed by joining u to an endpoint of a disjoint copy of the path Pn is graceful. Applying the theorem to spiders with legs L1, …, Ls obeying the stated length inequalities yields graceful labelings for those spiders. An explicit construction is given for the subfamily in which one leg may be arbitrarily long while every other leg has at most two edges, again with the center labeled zero.

What carries the argument

The relaxed graceful-joining construction that attaches a path Pn to a vertex u whose label is bounded above by n − floor(n/2) − 1 when n ≢ 1 (mod 4).

If this is right

  • Spiders whose leg lengths satisfy the doubling-plus-constant inequalities are graceful.
  • Spiders consisting of one long leg and several legs of length at most two admit explicit graceful labelings with the center at zero.
  • Further paths can be attached at the center of these explicitly labeled spiders while preserving gracefulness.

Where Pith is reading between the lines

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

  • The same joining technique may apply to spiders whose leg lengths obey weaker growth rules than the ones proved here.
  • The zero-center explicit labeling supplies a concrete starting point for checking gracefulness of mixed-leg spiders by computer for moderate sizes.

Load-bearing premise

The base graph G already possesses a graceful labeling in which the attachment vertex u carries a label small enough to satisfy the stated inequality with the chosen path length n.

What would settle it

A concrete spider obeying the leg-length inequalities for which the constructed edge differences are not all distinct would falsify the claim.

Figures

Figures reproduced from arXiv: 2605.14295 by Songling Shan, Yucheng Zhong.

Figure 1
Figure 1. Figure 1: An illustration of the labeling h. Next we verify that h(E(G′ )) = [1, m + n]. As h(x) = f(x) + ⌊ n 2 ⌋ for all x ∈ V (G) and f(E(G)) = [1, m], we have h(E(G)) = [1, m]. As g is an α-labeling of Pn, by the definition of h, we have h(E(Pn)) = m + 1 + [1, n − 1] = [m + 2, m + n]. Furthermore, we have h(u) = f(u) + ⌊ n 2 ⌋ and h(v) = g(v) + m + 1 = f(u) + ⌊ n 2 ⌋ + m + 1 since g(v) ≥ ⌊ n 2 ⌋, and so h(uv) = m… view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of naming the vertices of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A graceful labeling of S when s = 2 and ℓ = 11. For any i ∈ [1, s], let f(ui) = m − 2(i − 1), f(vi) = 2i − 1; and for any i ∈ [0, ℓ], let f(xi) =    2 × i 4 = i 2 if i ≡ 0 (mod 4), m − 2s − 2 × i−1 4 = m − 2s − i−1 2 if i ≡ 1 (mod 4), 2s − 1 + 2 × i+2 4 = 2s − 1 + i+2 2 if i ≡ 2 (mod 4), m − 1 − 2 × i−3 4 = m − 1 − i−3 2 if i ≡ 3 (mod 4). See [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A graceful labeling of S when s = 2 and ℓ = 10. In the remainder of the proof, we verify that f is a graceful labeling of S. Before proceed to the proof, we define a partition of V (S) and E(S) as follows. Let U = {ui : i ∈ [1, s]}, V = {vi : i ∈ [1, s]}, and Wj = {xi : i ∈ [1, ℓ], i ≡ j (mod 4)}, j ∈ [0, 3]; and E1 = {x0ui : i ∈ [1, s]}, E2 = {uivi : i ∈ [1, s]}, Fj = {xixi+1 : i ≡ j (mod 4)}, j ∈ [0, 3].… view at source ↗
read the original abstract

A \emph{graceful labeling} of a graph $G$ is an injective function $f : V(G) \to \{0, \ldots, |E(G)|\}$ such that $\{\,|f(u)-f(v)| : uv \in E(G)\,\} = \{1, \ldots, |E(G)|\}$. If such a labeling exists, then we call $G$ \emph{graceful}. Introduced by Rosa in 1967, graceful labeling has been widely studied, and the Graceful Tree Conjecture asserts that every tree is graceful. The conjecture is known to hold for several classes of trees, including caterpillars, trees with at most four leaves, trees of diameter at most five, and certain spiders. An important subclass is that of \emph{$\alpha$-labelings}, where a graceful labeling $f$ admits an integer $\alpha$ such that each edge joins a vertex with label at most $\alpha$ to one with label greater than $\alpha$. A result from 1982 by Huang, Kotzig, and Rosa shows that if $H$ has an $\alpha$-labeling with a vertex $u$ labeled $0$ or $\alpha$, and $G$ has a graceful labeling with a vertex $v$ labeled $0$, then identifying $u$ and $v$ yields a graceful graph, though this requires a $0$-labeled vertex in $G$. We prove a related result that relaxes this condition: if $G$ has a graceful labeling $f$ such that $f(u)+\lfloor n/2 \rfloor + 1 \le n$ and $n \not\equiv 1 \pmod{4}$, where $u\in V(G)$ and $n\ge 2$ is an integer, then joining $u$ to an end vertex of the vertex-disjoint $n$-vertex path $P_n$ yields a graceful graph. As an application, we show that any spider with legs $L_1,\ldots,L_s$ ($s \ge 1$) satisfying $|E(L_{2})| \ge 2|E(L_1)|+ 4$ and $|E(L_{i+1})| \ge 2|E(L_i)|+ 2$ for $i \in \{2,\ldots, s-1\}$ is graceful. Furthermore, we give an explicit graceful labeling for spiders with one leg of arbitrary length and all others of length at most two such that the center is labeled by $0$. This labeling enables the construction of larger graceful spiders by attaching paths at the center.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves a relaxed joining theorem: if G admits a graceful labeling f with vertex u satisfying f(u) + floor(n/2) + 1 ≤ n and n ≢ 1 (mod 4), then the graph obtained by joining u to an endpoint of a disjoint n-vertex path Pn is graceful. This is applied to show that any spider with legs L1,...,Ls (s≥1) satisfying |E(L2)| ≥ 2|E(L1)| + 4 and |E(Li+1)| ≥ 2|E(Li)| + 2 for i=2 to s-1 is graceful. The paper also supplies an explicit graceful labeling, with center labeled 0, for the family of spiders having one leg of arbitrary length and all remaining legs of length at most two.

Significance. If the constructions are correct, the work advances the Graceful Tree Conjecture by establishing gracefulness for two explicit infinite families of spiders via direct, reproducible labelings. The relaxed joining condition broadens the 1982 Huang-Kotzig-Rosa theorem by removing the requirement that the attachment vertex carry label 0 or α, thereby enabling the inductive arguments for the spider families. The explicit center-0 labeling for the second family is a particular strength, as it immediately supports further attachments.

minor comments (3)
  1. [§2] §2, Definition of the relaxed joining condition: the inequality f(u) + floor(n/2) + 1 ≤ n is stated without an accompanying small example (e.g., n=3 or n=5) that exhibits the explicit path labels and verifies that the new edge differences exactly fill {1,...,m+n} with no collisions.
  2. [§4] §4, Application to the second spider family: the explicit labeling with center 0 is described but the verification that the resulting labels remain injective and produce all required differences is only sketched; a table for a concrete instance (one leg of length 5, two legs of length 2) would make the construction easier to check.
  3. [References] References: the 1982 Huang-Kotzig-Rosa paper is cited only by year; the full bibliographic details (journal, volume, pages) should be supplied for completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the recognition of the relaxed joining theorem's utility, and the recommendation of minor revision. The assessment correctly identifies the broadening of the Huang-Kotzig-Rosa result and the value of the center-0 labeling for further attachments.

Circularity Check

0 steps flagged

Derivation is self-contained with independent constructions

full rationale

The paper proves a new relaxed joining theorem directly from the definition of graceful labeling by constructing an explicit labeling on the added path vertices that fills the missing differences without conflicts, under the stated numerical conditions on f(u) and n. This construction is verified case-by-case for the two spider families by exhibiting base labelings (including the center-0 case) that meet the hypothesis, with the leg-length inequalities ensuring the inductive attachment preserves the required bound. The 1982 Huang-Kotzig-Rosa result is cited only for context and is not invoked as a load-bearing premise; the new theorem relaxes rather than depends on it. No equations reduce to self-definitions, fitted inputs renamed as predictions, or self-citation chains. The argument consists of explicit constructions and direct verification against the graceful-labeling definition.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph theory definitions and a prior 1982 theorem; no free parameters, new entities, or ad hoc axioms are introduced beyond the domain assumptions of graceful labelings.

axioms (2)
  • domain assumption A graceful labeling is an injective function f from vertices to {0, ..., m} such that the absolute differences on edges exactly equal {1, ..., m}.
    This is the core definition invoked throughout the abstract for all claims.
  • standard math Graphs considered are finite, simple, and undirected trees or paths.
    Standard background assumption for the spider graphs and path attachments.

pith-pipeline@v0.9.0 · 6021 in / 1557 out tokens · 71042 ms · 2026-05-19T16:52:20.901620+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    Bahls, S

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

    work page 2010

  2. [2]

    R. Cattell. Graceful labellings of paths.Discrete Math., 307(24):3161–3176, Nov. 2007

    work page 2007

  3. [3]

    J. A. Gallian. A dynamic survey of graph labeling.Electronic Journal of Combinatorics, DS6, 2025. 28th edition, October 30, 2025

    work page 2025

  4. [4]

    S. W. Golomb. How to number a graph.Graph theory and computing, pages 23–37, 1972

    work page 1972

  5. [5]

    Hrnc´ ıar and A

    P. Hrnc´ ıar and A. Haviar. All trees of diameter five are graceful.Discrete Mathematics, 233:133–150, 2001

    work page 2001

  6. [6]

    Huang, A

    C. Huang, A. Kotzig, and A. Rosa. Further results on tree labelings.Utilitas Mathe- matica, 21:31–48, 1982

    work page 1982

  7. [7]

    Panpa, S

    A. Panpa, S. Imnang, and T. Wasuanankul. Graceful labeling of spider graphs with at most five legs.Journal of Applied Mathematics, page 5, 2025. 16

    work page 2025

  8. [8]

    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, 3:1–5, 2016

    work page 2016

  9. [9]

    Ringel.Theory of Graphs and Its Applications

    G. Ringel.Theory of Graphs and Its Applications. 1964

    work page 1964

  10. [10]

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

    work page 1966

  11. [11]

    A. Rosa. Labeling snakes.Ars Combinatoria, 3:67–74, 1977

    work page 1977

  12. [12]

    Saengsura and T

    K. Saengsura and T. Poomsa-ard. Graceful labeling of some spider graphs.European Journal of Pure and Applied Mathematics, 18(2):5305, 2025. 17

    work page 2025