{"id":"6a2c0675-a1aa-4796-865d-81cd3cb1b403","arxiv_id":"1908.06051","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper proves exact minimum coprime numbers for all generalized Petersen graphs GP(n,2), for stacked triangular and pentagonal prisms, and for a degree-two Petersen variant, while conjecturing the value for odd prisms.","lead":"This paper determines the smallest possible largest label in coprime labelings, where adjacent vertices receive coprime integers, for several families of generalized Petersen and prism graphs. It gives exact values for every generalized Petersen graph GP(n,2), for stacked triangular and pentagonal prisms, and conditional results for odd prisms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9's hand-verified case analysis is the load-bearing step for Theorem 10; a missed gcd interaction would break the formula, but no concrete error is apparent and a finite check can settle it.","rationale":"The reader's weakest assumption was exactly the exhaustiveness and correctness of Lemma 9's case analysis, and my review reaches the same conclusion: this is the most load-bearing step in the paper. The lower bounds in Lemma 9 and Theorem 10 depend only on the cited independence number α(GP(n,2)) = floor(4n/5), which is an external published result and, for the small cases I checked, correct. The novel and unverified part is the upper-bound construction. I traced through the cases involving cross-block reassignments (4b, 4c, 4d) and the final-block cases of Theorem 10; the gcd checks that are stated are valid, and the few adjacencies not explicitly listed are indeed trivially coprime (e.g., consecutive odd labels, or labels differing by 2 with both odd). I did not find a counterexample. However, the proof style—long case analysis, some omitted enumerations, a bound typo, and no machine check—leaves real residual risk. The proposed finite-period verification is decisive because the construction is periodic with period 5005 in the block index, so checking one full period is equivalent to checking all n. Thus my stress-test does not change the reader's CONDITIONAL verdict; it reinforces the condition and offers a concrete path to resolution.","tokens_in":22356,"tokens_out":29743,"duration_ms":207347,"concrete_test":"Write a program that, for each residue k modulo 5005, constructs the Lemma 9 labeling for GP(5m,2) exactly as prescribed by the case dispatch (Case 1, 2, 3a, 3b, 4a, 4b, 4c, 4d, including any modifications to block k−1) and verifies gcd(ℓ(x),ℓ(y)) = 1 for every edge of the graph. Separately, enumerate m modulo 35 and verify the Theorem 10 final-block labelings for n = 5m+1, 5m+2, 5m+3, 5m+4. Since every divisibility condition and every label is a linear function of k (resp. m) with period dividing 5005 (resp. 35), passing one full period proves the construction for all n. If every case passes, the upper bound is rigorously confirmed and the conditional verdict can be upgraded.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim, Theorem 10, gives an exact formula for pr(GP(n,2)) for all n. Its upper bound rests entirely on the constructive labeling in Lemma 9, whose proof is a 12-case analysis over divisibility by 5, 7, 11, and 13. The weakest point is the exhaustiveness and correctness of the gcd checks in Cases 4b–4d, where labels in the previous block are reassigned (e.g., v_{5k} and u_{5k} in Case 4b, plus u_{5k−2} in Case 4d). The proof asserts that 'there are ten adjacent pairs of labels that need to be verified' but does not always enumerate every edge incident to a reassigned vertex; for instance, Case 4c reassigns five vertices, whose neighbors generate thirteen distinct edges, and three of those gcds are only implicitly trivial. A missed interaction—say a pair of labels sharing a prime factor larger than 13, or a case where the periodicity argument for the previous block fails—would invalidate the formula for the affected residue class. I found no actual counterexample in review, and the case logic appears internally consistent, but the proof is not machine-checked and contains at least one typo (the bound '12m+1' at the end of Lemma 9). Because all conditions are periodic modulo 5·7·11·13 = 5005, the construction is amenable to exhaustive finite verification.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":22653,"tokens_out":39702,"duration_ms":316312,"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":[{"comment":"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.","section":"Section 6, Theorem 16, Eq. (6.1)"},{"comment":"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.","section":"Section 4, Lemma 9, Cases 4c and 4d"},{"comment":"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.","section":"Section 5, Theorem 14, Table 3"}],"minor_comments":[{"comment":"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.","section":"Section 4, Lemma 9, final sentence"},{"comment":"The sentence 'Therefore, pr(GP(n,3)) = 12m+7' should refer to GP(n,2), not GP(n,3).","section":"Section 4, Theorem 10, case n = 5m+3"},{"comment":"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.","section":"Section 6, Theorem 16"},{"comment":"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.","section":"Section 3, Theorems 3-7"},{"comment":"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.","section":"Section 4, Theorem 10, lower bounds"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The main mathematical contribution, Theorem 10, appears defensible, and the issue in Lemma 9 is a matter of completing the verification. The serious problem is Theorem 16: the constructed labeling is demonstrably not a prime labeling for k=7, so the proof as written is invalid. The authors should be asked to fix or remove that theorem; if the statement is true, they need a substantially extended case analysis. The finite checks in Theorem 14 and Lemma 9 would also benefit from machine verification."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: the paper's main result, the exact formula for pr(GP(n,2)) for all n, appears to be correct, and the block-construction is a genuinely new technique. It deserves a real referee, but it also needs a cleanup pass before publication.\n\nWhat's new: exact formulas for GP(n,2), the stacked triangular and pentagonal prisms, and the variation GP*(2k,k). The lower bounds come from independence numbers; the upper bounds are explicit labelings. The central construction in Lemma 9 is detailed and, as far as I could see, correct. The periodic extension argument for Y5,n is sound: adjacent labels differ by at most 10, so only primes 2,3,5,7 matter, and shifting by 420 preserves coprimality. Theorem 16's prime labeling for odd k is a nice piece of work.\n\nThe soft spots are all in the verification layer, not in the main ideas. The Lemma 9 case analysis is long and hand-checked; the cross-block cases 4b–4d reassign labels in the previous block, and the proof doesn't always enumerate every affected edge. I found no actual counterexample, and because the conditions are periodic modulo 5005, a finite computer check would settle it. The paper should either provide that check or expand the enumeration. There are also a few typos: the bound '12m+1' at the end of Lemma 9 should read '12m-1', and Theorem 10's case n=5m+3 says GP(n,3) instead of GP(n,2). Theorem 16's argument for non-primality when k is even is muddled as written; it leans on 'less than k even labels' and then transitions to the coprime construction, but the counting logic needs rewording to be convincing. Finally, the appendix theorems 17–23 omit the verification, saying the pattern is clear from the tables; for full rigor, those tables should be accompanied by at least a sketch or a verifiable script.\n\nThe citation pattern is fine. The self-citation to [1] is context, not padding. The external independence-number formulas are applicable.\n\nWho this is for: anyone working on graph labelings, especially the minimum-coprime variant. It extends a small but active program of Berliner et al. and Asplund–Fox. It won't change the field, but it's a solid, checkable contribution.\n\nRecommendation: send it to a serious referee. The core results are correct and new; the typos and the unverified case analysis are fixable, and a referee with a little patience can verify the finite checks. If the authors add the modulo-5005 verification and tighten the appendix, this is an accept.","headline":"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.","tokens_in":23189,"tokens_out":3052,"would_cite":false,"duration_ms":27708,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C78","05C69"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["coprime labeling","prime labeling","minimum coprime number","generalized Petersen graph","prism graph","stacked prism graph","independence number","graph labeling"],"falsifier":"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.","tokens_in":22160,"feed_emoji":"🔢","tokens_out":8729,"duration_ms":71441,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact coprime labeling found for every GP(n,2)","feed_subtitle":"Five formulas, one per n mod 5, give the smallest possible largest label for the k=2 case.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the independence number formula α(GP(n,2)) = ⌊4n/5⌋ that fixes the lower bound in Lemma 9 and Theorem 10.","marker":"[2]"},{"why":"Provides the lemma that a prime graph needs α(G) ≥ |V|/2, which rules out prime labelings and drives the parity bounds.","marker":"[7]"},{"why":"Introduces minimum coprime labelings and the parameter pr(G), the object the paper computes.","marker":"[3]"},{"why":"States the prime-pair conjecture and computational verification that underlies the conditional prism results and Conjecture 8.","marker":"[13]"}],"fun_headline_variants":["Closed form for GP(n,2) coprime number","Five residue formulas solve GP(n,2) labeling","GP(n,2) coprime number: exact for all n","Minimum coprime labeling fully determined for GP(n,2)","Exact coprime number for every generalized Petersen GP(n,2)"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Closed form for GP(n,2) coprime number","Five residue formulas solve GP(n,2) labeling","GP(n,2) coprime number: exact for all n","Minimum coprime labeling fully determined for GP(n,2)","Exact coprime number for every generalized Petersen GP(n,2)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000366,"raw_usage":{"total_tokens":1913,"prompt_tokens":837,"completion_tokens":1076,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":453,"completion_tokens_details":{"reasoning_tokens":996}},"tokens_in":453,"tokens_out":1076,"duration_ms":9271,"temperature":1.0,"reasoning_tokens":996,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:58:58.688105+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Behsaz, P","cited_arxiv_id":null,"evidence_quote":"Supplies the independence number formula α(GP(n,2)) = ⌊4n/5⌋ that fixes the lower bound in Lemma 9 and Theorem 10."},{"cited_title":"Fu and K.-C","cited_arxiv_id":null,"evidence_quote":"Provides the lemma that a prime graph needs α(G) ≥ |V|/2, which rules out prime labelings and drives the parity bounds."},{"cited_title":"Berliner, N","cited_arxiv_id":null,"evidence_quote":"Introduces minimum coprime labelings and the parameter pr(G), the object the paper computes."},{"cited_title":"Schluchter, J","cited_arxiv_id":null,"evidence_quote":"States the prime-pair conjecture and computational verification that underlies the conditional prism results and Conjecture 8."}],"review_version":1}