pith. sign in

arxiv: 2601.12574 · v2 · submitted 2026-01-18 · 🧮 math.CO

L(3,2,1)-labelings of three classes of 4-valent circulants

P\v{r}emysl Holub , Martin Kop\v{r}iva This is my paper

Pith reviewed 2026-05-16 12:43 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C7805C15
keywords L(3,2,1)-labelingcirculant graphminimum spangraph distancechannel assignment4-valent graph
0
0 comments X

The pith

The exact minimum span for L(3,2,1)-labelings is determined for all circulant graphs C_n(1,3), C_n(1,4), and C_n(1,5).

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

The paper determines the smallest range of labels that can be assigned to the vertices of these 4-regular circulant graphs so that vertices at distance 1 receive labels differing by more than 3, at distance 2 by more than 2, and at distance 3 by more than 1. It does so by constructing explicit labelings that achieve a candidate span and proving matching lower bounds that hold for every n. The work extends earlier results on the square of the cycle by handling the additional chord lengths t=3,4,5 separately. A reader cares because these exact values give the tightest possible frequency separation required in networks whose connectivity is a circulant with those steps.

Core claim

For each family C_n(1,t) with t in {3,4,5}, the minimum span λ_{(3,2,1)}(C_n(1,t)) equals a concrete expression in n that is realized by a periodic assignment of labels around the cycle and shown to be best possible by a distance-based counting argument that rules out any smaller range.

What carries the argument

The distance-dependent separation rule |f(x)−f(y)| > 3−dist(x,y) together with the cyclic symmetry of the circulant that permits reduction of the labeling problem to a finite set of residue classes modulo small integers.

If this is right

  • The channel-assignment problem for these networks has a known optimal label range for every order n.
  • Periodic labelings achieve optimality, so the same pattern repeats every few vertices.
  • The separation conditions for distances 1, 2, and 3 can be satisfied simultaneously within the stated span.
  • The three families can be handled uniformly once the appropriate modulus for each t is fixed.

Where Pith is reading between the lines

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

  • The same modular-construction technique may extend to other fixed t or to circulants with more generators.
  • If the span grows linearly with n, the per-vertex label density remains bounded, which would be useful for large-scale network design.
  • Lower-bound techniques based on counting vertices inside distance-3 balls could be reused for L(s, t, u) labelings with different parameters.

Load-bearing premise

That case-by-case constructions modulo a small integer together with a matching lower-bound argument suffice to cover every sufficiently large n in each of the three families.

What would settle it

An explicit n and a labeling of C_n(1,t) whose span is strictly smaller than the claimed value, or a proof that no labeling of that span exists for some n.

read the original abstract

An $L(3,2,1)$-labeling of a graph $G$ is an assignment $f$ of nonnegative integers to vertices such that $\vert f(x)-f(y)\vert > 3-\mbox{dist}_G(x,y)$ for every pair $x,y$ of vertices of $G$, where $\mbox{dist}_G(x,y)$ denotes the distance between $x$ and $y$ in $G$. The minimum span (i.e., the difference between the largest and the smallest value) among all $L(3,2,1)$-labelings of $G$ is denoted by $\lambda_{(3,2,1)}(G)$. In this paper, we study $L(3,2,1)$-labelings of three classes of circulant graphs. Namely, we investigate $\lambda_{(3,2,1)}$ of circulant graphs $C_n(1,t)$, where $t\in\{3,4,5\}$ and $n$ is the order of the graph. This paper is a continuation of a recent publications of V. Bianco and T. Calamoneri who studied the square of cycles, i.e., circulant graphs $C_n(1,2)$.

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 / 4 minor

Summary. The paper determines λ_{(3,2,1)}(C_n(1,t)) for t ∈ {3,4,5} and all sufficiently large n. It supplies explicit periodic labelings (with periods dividing 6 or 8) that realize a concrete span together with matching lower bounds obtained from the cardinality of distance-3 balls and the set of forbidden differences; the argument proceeds by exhaustive case analysis on n modulo a small integer and direct verification that the constructed assignments satisfy the strict separation conditions for all pairs at graph distance 1, 2 or 3.

Significance. The work extends the earlier exact determination for squares of cycles (C_n(1,2)) to three additional infinite families of 4-regular circulants. The combination of closed-form constructions, parameter-free lower bounds, and exhaustive modular case analysis constitutes a concrete advance in distance-constrained labeling of vertex-transitive graphs; such results are directly applicable to frequency-assignment problems on circulant networks.

minor comments (4)
  1. [§3.1] §3.1: the definition of the periodic labeling for t=3 is given only for n ≡ 0,1,2,3,4,5 mod 6; an explicit statement that the same pattern works for all larger n in each class would remove any ambiguity about the base cases.
  2. [Table 1] Table 1: the column headings list the achieved span but do not indicate the period of the labeling; adding this information would make the table self-contained.
  3. [§4.2] §4.2: the lower-bound proof for t=5 invokes the size of a distance-3 ball but does not explicitly compute the number of distinct forbidden differences when n is even; a short sentence clarifying that the ball is induced and contains no extra edges would help.
  4. [References] The bibliography entry for Bianco–Calamoneri is cited as “a recent publication” but lacks the year and journal; supplying the full reference is required for archival completeness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary of our manuscript and for recommending minor revision. The referee's description accurately reflects the scope and methods of the paper, which extends prior results on L(3,2,1)-labelings from C_n(1,2) to the families C_n(1,t) for t=3,4,5. No specific major comments were provided in the report, so we have no individual points to address. We are prepared to make any editorial or minor clarifications requested by the editor.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The manuscript supplies explicit periodic labelings for C_n(1,t) with t in {3,4,5} together with matching lower bounds obtained directly from the cardinality of distance-3 balls and the forbidden differences required by the L(3,2,1) condition. The exhaustive case division on n modulo small constants (typically 6 or 8) is performed for all sufficiently large n and verified by direct checking that the constructed assignments meet the strict inequalities for all pairs at distances 1, 2 and 3. No equation or claim reduces the target span to a fitted parameter, a self-referential definition, or a load-bearing self-citation; the derivation chain remains self-contained combinatorial constructions and independent lower-bound arguments.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definitions of circulant graphs, graph distance, and the L(3,2,1) separation condition. No free parameters, new axioms, or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of circulant graphs C_n(S) and shortest-path distance in undirected graphs.
    Invoked implicitly when defining the graphs and the labeling condition.

pith-pipeline@v0.9.0 · 5533 in / 1161 out tokens · 39029 ms · 2026-05-16T12:43:45.641431+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Bianco, T

    V. Bianco, T. Calamoneri,L(3,2,1)-labeling of the square of cycles, Theoretical Comp. Science1060(2026), 115629

    work page 2026

  2. [2]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty,Graph Theory, Springer-Verlag London, 2008

    work page 2008

  3. [3]

    Burkhard, W

    R.E. Burkhard, W. Sandholzer,Efficiently solvable special case of bottleneck travelling salesman problem, Discrete Appl. Math.32(1991), 61-76

    work page 1991

  4. [4]

    ˇCada, J

    R. ˇCada, J. Ekstein, P. Holub, O. Togni,Radio labelings of distance graphs, Discrete Appl. Math.161(2013), 2876-2884

    work page 2013

  5. [5]

    Calamoneri,The L(h,k)-labelling problem: an updated survey and annotated bib- liography, The Computer J.54/8(2011), 1344-1371

    T. Calamoneri,The L(h,k)-labelling problem: an updated survey and annotated bib- liography, The Computer J.54/8(2011), 1344-1371

    work page 2011

  6. [6]

    Calamoneri,L(3,2,1)-labeling of certain planar graphs.Theor

    T. Calamoneri,L(3,2,1)-labeling of certain planar graphs.Theor. Comp. Science 1022(2024), 114881

    work page 2024

  7. [7]

    Chartrand, D

    G. Chartrand, D. Erwin, P. Zhang, F. Harary,Radio labelings of graphs, Bull. Inst. Combin. Appl.33(2001), 77-85

    work page 2001

  8. [8]

    M.L. Chia, D. Kuo, H. Liao, C.H. Yang, R.K. Yeh,L(3,2,1)-labeling of graphs, Taiwanese Journal of Mathematics15/6(2011), 2439-2457

    work page 2011

  9. [9]

    Clipperton, J

    J. Clipperton, J. Gehrtz, Z. Szaniszlo, D. Torkornoo,L(3,2,1)-Labeling of Simple Graphs, Valparaiso Experience in Research by Undergraduate Mathematicians, Val- paraiso University, 2006

    work page 2006

  10. [10]

    Das, S.C

    S. Das, S.C. Ghosh, S. Nandi,OptimalL(3,2,1)-labeling of triangular lattice, Discrete Appl. Math.228(2017), 32-40

    work page 2017

  11. [11]

    Griggs, R.K

    J.R. Griggs, R.K. Yeh,Labeling graphs with a condition at distance 2, SIAM J. Disc. Math.5/4(1992), 586-595

    work page 1992

  12. [12]

    Hale,Frequency assignment: theory and applications, Proceedings of the IEEE 68/12(1980), 1497-1514

    W.K. Hale,Frequency assignment: theory and applications, Proceedings of the IEEE 68/12(1980), 1497-1514

    work page 1980

  13. [13]

    Holub, M

    P. Holub, M. Kopˇ riva,OnL(3,2,1)-labelings of circulant graphs. Preprint

    work page

  14. [14]

    Korˇ ze, Z

    D. Korˇ ze, Z. Shao, A. Vesel,New results on radiok-labelings of distance graphs, Discrete Appl. Math.319(2022), 472-479

    work page 2022

  15. [15]

    Meijer,Connectivities and diameters of circulant graphs, MSc

    P.T. Meijer,Connectivities and diameters of circulant graphs, MSc. Thesis Simon Fraser University, 1991

    work page 1991

  16. [16]

    Mitra, S

    S. Mitra, S. Bhoumik,L(2,1)-labeling of circulant graphs, Discuss. Math. Graph Theory39(2019), 143-155

    work page 2019

  17. [17]

    Mitra, S

    S. Mitra, S. Bhoumik,L(3,1)-labeling of circulant graphs, Discrete Math., Algor. and Applic.14(2022), 2150093 (12 pages). 19

    work page 2022

  18. [18]

    Mitra, S

    S. Mitra, S. Bhoumik,L(h, k)-labeling of circulant graphs, J. Appl. Math. and Physics 11/5(2023), 1448-1458

    work page 2023

  19. [19]

    J. J. Sylvester,On subinvariants, i. e. semi-invariants to binary quantics of an un- limited order, American Journal of Mathematics5(1882), 79-136

    work page

  20. [20]

    F. Tao, G. Gu,L(2,1)-labeling problem on distance graphs, J. Southeast Univ. (En- glish Ed.)20/1(2004), 122-125

    work page 2004

  21. [21]

    Yeh,A survey on labeling graphs with a condition at distance two, Discrete Math.306(2006), 1217-1231

    R.K. Yeh,A survey on labeling graphs with a condition at distance two, Discrete Math.306(2006), 1217-1231

    work page 2006

  22. [22]

    Journal of Computational and Graphical Statistics , author =

    X. Zhang: OptimalL(3,2,1)-labeling of trees. AKCE Int. Journal of Graphs and Combin. https://doi.org/10.1080/09728600.2024.2358691 20 Appendix - patterns In this appendix, we list patterns for sparse circulants mentioned in Tables 1, 2, 3, 4 and 5. Cn({1,3,n−3,n−1}) n λ(3,2,1) pattern 7 12 0,6,12,4,10,2,8, 8 15 0,9,2,11,4,13,6,15, 9 16 0,4,8,12,16,2,6,10,...

    work page doi:10.1080/09728600.2024.2358691 2024