Pith. sign in

REVIEW 3 major objections 6 minor 14 references

Minimum Coprime Labelings of Generalized Petersen and Prism Graphs

T0 review · 3 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper proves an exact formula for the minimum coprime number of every generalized Petersen graph GP(n,2), and supplements this with exact values for stacked prisms and a prime/coprime dichotomy for a generalized Petersen variant.

desk verdict Solid new exact results for minimum coprime labelings; the GP(n,2) formula is right but rests on a hand-checked case analysis that deserves machine verification. read the letter →

arxiv 1908.06051 v1 pith:OS5CHSZW submitted 2019-08-16 math.CO

John Asplund , N. Bradley Fox This is my paper · ORCID
classification math.CO MSC 05C7805C69
keywords coprimelabelingprimeminimumnumbergeneralizedPetersengraphprismstackedindependence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

A graph with n vertices admits a prime labeling when the labels can be the integers 1 through n, but many graphs fail this test; the paper asks how much larger the largest label must become for adjacent vertices to still receive relatively prime labels. The core result is an exact answer for every generalized Petersen graph of the form GP(n,2), where the minimum coprime number is one of the five linear expressions 12m−1, 12m+3, 12m+5, 12m+7, or 12m+9 depending on whether n = 5m, 5m+1, ..., 5m+4. The proof labels the graph in blocks of ten vertices, then repairs the rare conflicts by hand in a case analysis keyed to divisibility of the block labels by 5, 7, 11, and 13. Alongside this, the paper gives exact values for stacked prisms Y3,n and Y5,n, a prime/coprime dichotomy for a variant GP*(2k,k), and conditional results for odd prism graphs that would become unconditional for all odd n if a known prime-pair conjecture holds.

What carries the argument

The load-bearing mechanism is a block construction for GP(n,2) that groups five consecutive v-vertices and five consecutive u-vertices into a block and assigns the labels 12k+1 through 12k+11 according to the pattern in Equation (4.1). A case analysis (Lemma 9 Cases 1–4d) repairs the few edges whose labels could share a factor by swapping labels, with the cases determined by divisibility of 12k−1, 12k−3, and 12k+5 by 5, 7, 11, and 13; the lower bound is fixed by the independence-number formula ⌊4n/5⌋ and the resulting parity constraint on even labels.

What would settle it

Run an exhaustive backtracking search for n=5 and n=10 asking whether GP(n,2) admits any coprime labeling whose largest label is smaller than the value claimed (11 for n=5, 23 for n=10); because the parity count is tight, any success would immediately falsify Theorem 10, while confirming these two bases plus checking Lemma 9's gcd conditions for every k in the residue classes where 5, 7, 11, or 13 divides 12k−1 or 12k−3 would settle the formula.

Watch

Extended reading notes

Core claim

For every n≥5 the minimum coprime number of GP(n,2) is pr(GP(n,2)) = 12m−1 if n=5m, 12m+3 if n=5m+1, 12m+5 if n=5m+2, 12m+7 if n=5m+3, and 12m+9 if n=5m+4. The construction labels v1,...,vn, u1,...,un by first placing blocks of ten labels matching the residue classes of 12k+1 through 12k+11, and the lower bound comes from the independence number α(GP(n,2)) = ⌊4n/5⌋, which limits how many even labels can be placed on independent vertices. The paper further proves pr(Y3,n)=4n−1, pr(Y5,n)=6n−1, and that GP*(2k,k) is prime exactly when k is odd, with pr=4k+1 when k is even.

Load-bearing premise

The whole argument for GP(n,2) rests on the hand-checked case analysis in Lemma 9 being exhaustive and correct, especially the cross-block reassignments in Cases 4b through 4d, together with the known independence number formula α(GP(n,2)) = ⌊4n/5⌋ used for the lower bound.

Editorial extensions

If this is right

  • For the infinite family GP(n,2), the minimum coprime number is now known exactly for all n≥5, so no further parity or independence obstruction can lower the largest label.
  • The ratio of the minimum coprime number to the number of vertices approaches 6/5 within GP(n,2), since pr ≈ 12n/5 on 2n vertices.
  • The block-labeling method, combined with known independence numbers, gives explicit conjectures for GP(n,3) and GP(3k,k), leaving only the constructions open.
  • For odd prism graphs GP(n,1), the paper reduces the conjecture pr=2n+1 for all odd n to the existence, for each even N, of primes N+s and 2N+s; this makes the full conjecture conditional on that prime-pair conjecture.
  • The exact stacked-prism values pr(Y3,n)=4n−1 and pr(Y5,n)=6n−1 confirm that the independence number alone dictates the answer for these graphs, supporting the conjecture for all odd (2k+1)-gons.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The periodic structure of the case analysis suggests the Lemma 9 construction could be verified mechanically by checking finitely many residue classes of k modulo 5·7·11·13, which would settle any lingering doubt about exhaustiveness without changing the formula.
  • If the block method extends, the same style of answer for GP(n,3) would likely be a linear expression in n with a denominator matching the independence number's denominator, mirroring the 5-block used for k=2.
  • A counterexample to the prime-pair conjecture used for prisms would not touch the GP(n,2) result; the two parts of the paper rest on independent assumptions, so Theorem 10 stands even if the prism conjecture fails.
  • The GP*(2k,k) result suggests a boundary phenomenon: as the spoke-matching degenerates, the prime-labeling obstruction disappears exactly when the independence number reaches |V|/2, tying the parity dichotomy to a known necessary condition rather than to a new obstruction.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper studies coprime labelings of graphs, where adjacent vertices must receive relatively prime labels and the goal is to minimize the largest label, denoted pr(G). The main results are: several families of prism graphs GP(n,1) are shown to have pr(GP(n,1)) = 2n+1 under arithmetic hypotheses, with a conjecture for all odd n; an exact formula is claimed for pr(GP(n,2)) for every n ≥ 5, built on a block construction for GP(5m,2) and extensions to the other residue classes; exact formulas are claimed for stacked triangular and pentagonal prisms; and a variant GP*(2k,k) is analyzed. The arguments are explicit constructions together with lower bounds derived from independence numbers.

Significance. If correct, Theorem 10 is a valuable exact result: it determines the minimum coprime number for every generalized Petersen graph with k=2. The constructions are explicit and checkable, and the lower-bound arguments via independence numbers are parameter-free and concrete. The stacked-prism results and the study of GP* are also useful contributions. However, the proof of Theorem 16 contains a genuine gap for odd k ≥ 7, and the verification of Lemma 9's case analysis is not fully written out, so the paper needs substantive revision before the claims can be accepted.

major comments (3)
  1. [Section 6, Theorem 16, Eq. (6.1)] The proof of part (1) applies the swap cases only to values a = l(vi) with i odd in {1,...,k}. But the edges v_{i+k}v_{i+1+k} with i even also have labels differing by 7 and can be both divisible by 7. Concretely, for k=7 the labeling in Eq. (6.1) gives l(v13)=21 and l(v14)=28; these vertices are adjacent and both are divisible by 7, while none of the values l(v1), l(v3), l(v5), l(v7), namely 1, 9, 17, 25, is divisible by 7, so no swap case is triggered. Thus the labeling constructed in the proof is not prime, and the proof of Theorem 16(1) is incomplete. The case analysis must be extended to all edges with label difference 7, or the theorem needs a different proof.
  2. [Section 4, Lemma 9, Cases 4c and 4d] Case 4c states that 'there are ten additional pairs of labels that need to be shown to be relatively prime', but the five reassigned vertices v_{5k}, u_{5k}, u_{5k+2}, u_{5k+3}, v_{5k+4} have thirteen incident edges. The pairs (12k-1, 12k-3), (12k-1, 12k-4), and (12k-3, 12k-2) are not listed. Each of these gcds is indeed 1 by a short argument, so this is a presentation gap rather than a false construction; nevertheless, since Lemma 9 is the sole support for the exact formula in Theorem 10, the enumeration should be made complete and explicit, or backed by a short finite verification.
  3. [Section 5, Theorem 14, Table 3] The proof rests on the assertion that the 70-row labeling in Table 3 is coprime and has maximum adjacent-label difference 10, but the table is printed without the promised bold formatting and no verification is shown. Because the theorem claims an exact formula for all n, the key finite check should be supplied in a reproducible form, either by listing the 46 reassigned labels explicitly or by providing a short verifier script.
minor comments (6)
  1. [Section 4, Lemma 9, final sentence] The displayed upper bound 'pr(GP(5m,2)) ≤ 12m + 1' should read '12m - 1'; with the printed bound the chain '≤ 12m+1' and '≥ 12m-1' does not yield the equality stated.
  2. [Section 4, Theorem 10, case n = 5m+3] The sentence 'Therefore, pr(GP(n,3)) = 12m+7' should refer to GP(n,2), not GP(n,3).
  3. [Section 6, Theorem 16] The sentence 'our only concern with the labeling is when ui and ui+1 are both divisible by 7' is likely a typo for 'vi and vi+1', since the graph GP*(2k,k) has no edges of the form ui ui+1.
  4. [Section 3, Theorems 3-7] The symbol n is used both for the order of the prism and inside expressions such as l(un)=12n-1 in Lemma 9; the notation is understandable after setting n=5m, but the convention should be stated explicitly.
  5. [Section 4, Theorem 10, lower bounds] The lower-bound arguments for n = 5m+r are very compressed; spelling out the odd-label count would improve readability, e.g., for n=5m+1 the graph has 10m+2 vertices and α=4m, so at least 6m+2 odd labels are needed and the largest label is forced to be at least 12m+3.
  6. [Throughout] There are several minor language slips ('alludes us' for 'eludes us', 'the lables' for 'the labels', and some dangling references such as 'resulting in the relatively prime condition being satisfied'); a careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: explicit labelings plus external independence numbers; no fitted inputs or self-citation load-bearing.

full rationale

The derivation chain is not circular. The central claims are proved by explicit labelings constructed from the definitions, with lower bounds obtained from the externally cited independence-number formula alpha(GP(n,2)) = floor(4n/5) from Behsaz et al. [2]. In Lemma 9, the labeling for GP(5m,2) is built block-by-block using Equation (4.1) and then modified according to divisibility cases; the upper bound is obtained by direct gcd checks of adjacent labels, and the lower bound follows because alpha = 4m forces at least 6m odd labels, so the largest label cannot be below 12m-1. This is not circular: the independence number is an external theorem, not derived from the labeling, and the labeling is constructed rather than fitted to the target value. Theorem 10 extends the same construction to n = 5m+r by explicitly labeling the remaining r vertices and checking the finitely many cross-block adjacencies; lower bounds again use the same external independence formula. No parameter is fitted to the claimed result, and no 'prediction' is derived from the quantity it predicts. The self-citation to Asplund and Fox [1] is contextual background about earlier minimum coprime number results and is not load-bearing for Lemma 9 or Theorem 10. The hand-verified case analysis in Lemma 9 and the apparent typo '12m + 1' in the final inequality are correctness or exposition concerns, not circularity: all conditions are explicit, and the construction is amenable to finite verification. The other sections, including stacked prisms and GP*(2k,k), likewise use explicit labelings and structural parity/independence arguments. Therefore the paper is self-contained against external benchmarks and warrants score 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters: all labelings are explicit constructions, and the graph parameters m, n, k are inputs, not fitted values. No new entities are postulated. The central claims rest on cited independence-number formulas and on the correctness of exhaustive case analyses.

assumptions (4)
  • standard math Lemma 1 (Fu-Huang): If a graph G is prime, then α(G) ≥ |V(G)|/2.
    Used throughout to rule out prime labelings and to derive lower bounds on the minimum coprime number, e.g., Section 2.
  • domain assumption α(GP(n,2)) = floor(4n/5), from Behsaz-Hatami-Mahmoodian [2].
    Provides the lower bound in Lemma 9 and Theorem 10; the paper does not re-derive this formula.
  • domain assumption The number-theoretic conjecture of Schluchter et al. [13] that for even n there exists s with n+s and 2n+s prime, verified up to 2.468e9.
    Used to support Conjecture 8 for odd n up to that bound; not needed for the unconditional theorems.
  • domain assumption For Y3,n and Y5,n, α(Y3,n) = n and α(Y5,n) = 2n.
    Simple counting on each cycle; used for the lower bounds pr ≥ 4n-1 and pr ≥ 6n-1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum Coprime Labelings of Generalized Petersen and Prism Graphs." pith.science (2026). https://pith.science/paper/OS5CHSZW

@misc{pith2026190806051,
  author       = {Pith},
  title        = {Pith review of: Minimum Coprime Labelings of Generalized Petersen and Prism Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OS5CHSZW}},
  note         = {Machine review of arXiv:1908.06051}
}
abstract

A coprime labeling of a graph of order $n$ is an assignment of distinct positive integer labels in which adjacent vertices have relatively prime labels. Restricting labels to only the set $1$ to $n$ results in a prime labeling. In this paper, we consider families of graphs in which a prime labeling cannot exist with the goal being to minimize the largest value of the labeling set, resulting in a minimum coprime labeling. In particular, prism graphs, generalized Petersen graphs with $k=2$, and stacked prism graphs are investigated for minimum coprime labelings.

Figures

Figures reproduced from arXiv: 1908.06051 by the authors.

Figure 1
Figure 1. Minimum coprime labeling for GP(11,1) Proof. Label v1, . . . , vn as 1, . . . , n and u1, . . . , un with n + 1, . . . , 2n − 1, 2n + 1 respectively. All adjacent pairs in {v1, . . . , vn} and in {u1, . . . , un} have consecutive labels except for v1vn, un−1un, and u1un. The first pair includes 1 as one of the labels, and the second pair is labeled by consecutive odd labels. Lastly, u1un have relatively prime labels… view at source ↗
Figure 2
Figure 2. Visual representation of the labeling described in Equation (4.1) [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Example of a minimum coprime labeling of [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Example of a minimum coprime labeling of [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]
Figure 5
Figure 5. Figure 5: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1724 25 32 33 41 20 2126 29 36 37 38 35 30 272219 39 34 31 2823 18 [PITH_FULL_IMAGE:figures/full_fig_p015_5.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages

  1. [1]

    Asplund and N

    J. Asplund and N. B. Fox, Minimum coprime labelings for operations on graphs , Integers 19 (2019), 1–26

    work page 2019

  2. [2]

    Behsaz, P

    B. Behsaz, P. Hatami, and E. Mahmoodian, On minimum vertex covers of generalized Petersen graphs, Australas. J. Combin. 40 (2008), 253–264

    work page 2008

  3. [3]

    Berliner, N

    A. Berliner, N. Dean, J. Hook, A. Marr, A. Mbirika, and C. McBee, Coprime and prime labelings of graphs, J. Integer Seq. 19 (2016), no. 5, Article 16.5.8, 14. MR 3514551

    work page 2016

  4. [4]

    Besharati, J

    N. Besharati, J. B. Ebrahimi, and A. Azadi, Independence number of generalized Petersen graphs , Ars Combin. 124 (2016), 239–255

    work page 2016

  5. [5]

    Dean, Proof of the prime ladder conjecture , Integers 17 (2017), 1–9

    N. Dean, Proof of the prime ladder conjecture , Integers 17 (2017), 1–9

    work page 2017

  6. [6]

    J. Fox, R. Gera, and P. St˘ anic˘ a,The independence number number for the generalized Petersen graphs, Ars Combin. 103 (2012), 439–451

    work page 2012

  7. [7]

    Fu and K.-C

    H.-L. Fu and K.-C. Huang, On prime labelling , Discrete Math. 127 (1994), 181–186. 17

    work page 1994

  8. [8]

    J. A. Gallian, A dynamic survey of graph labeling , Electron. J. Combin. DS6 (2014)

    work page 2014

Show all 14 references
  1. [9]

    Haque, X

    K. Haque, X. Lin, Y. Yang, and P. Zhao, On the prime labeling of generalized Petersen graph P (n, 1), Util. Math. 83 (2010), 95–106

    2010

  2. [10]

    , On the prime labeling of generalized Petersen graphs P (n, 3), Int. J. Contemp. Math. Sciences 6 (2011), no. 36, 1783–1800

    2011

  3. [11]

    Lee, Minimum coprime graph labelings , arXiv preprint:1907.12670 (2019)

    C. Lee, Minimum coprime graph labelings , arXiv preprint:1907.12670 (2019)

    2019 arXiv

  4. [12]

    Prajapati and S

    U. Prajapati and S. Gajjar, Prime labeling of generalized Petersen graph , International Journal of Mathematics and Soft Computing 5 (2015), no. 1, 65–71

    2015

  5. [13]

    Schluchter, J

    S. Schluchter, J. Schroeder, K. Cockus, R. Ellingson, H. Harris, E. Rarity, and T. Wilson, Prime labelings of generalized Petersen graphs , Involve 10 (2017), no. 1, 109–124

    2017

  6. [14]

    A. Tout, A. N. Dabboucy, and K. Howalla, Prime labeling of graphs , Nat. Acad. Sci. Letters 11 (1982), 365–368. A Additional Generalized Petersen Results For Theorems 17-23, the proof for why the labeling is a coprime labeling is omitted as the pattern is clearly given in the ...

    1982

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.