[1,2]-Domination in Generalized Petersen Graphs

Fairouz Beggas; Hamamache Kheddouci; Mohammed Haddad; Volker Turau

arxiv: 1906.11966 · v1 · pith:M5TSW4ELnew · submitted 2019-06-27 · 💻 cs.DM · math.CO

[1,2]-Domination in Generalized Petersen Graphs

Fairouz Beggas , Volker Turau , Mohammed Haddad , Hamamache Kheddouci This is my paper

Pith reviewed 2026-05-25 13:23 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords [1,2]-dominationgeneralized Petersen graphsdomination numbertotal dominationP(n,2)graph parameters

0 comments

The pith

The [1,2]-domination number and [1,2]-total domination number of every generalized Petersen graph P(n,2) are determined exactly.

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

The paper computes the smallest size of a [1,2]-dominating set in the graphs P(n,2), where such a set requires every vertex outside it to be adjacent to one or two members. It likewise computes the minimum size under the total variant, which adds the condition that the set itself has no isolated vertices. These exact values close an open parameter question for an infinite family of vertex-transitive graphs. The results matter because they turn an optimization task over symmetric networks into a direct lookup or formula for any n.

Core claim

For the generalized Petersen graphs P(n,2), both the [1,2]-domination number γ_{[1,2]}(P(n,2)) and the [1,2]-total domination number are determined by explicit constructions and matching lower bounds that together give the precise minimum cardinality for every n.

What carries the argument

A [1,2]-dominating set, a vertex subset S such that every vertex outside S has exactly one or two neighbors in S.

If this is right

For every n the exact minimum number of vertices needed is now known.
Concrete constructions achieve the stated sizes and serve as upper bounds.
The same determination holds for the total-domination variant.
No smaller sets exist once the matching lower-bound arguments are accepted.

Where Pith is reading between the lines

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

The same case-division approach may transfer to other families such as P(n,k) for fixed k greater than 2.
The formulas could be used to test conjectures about [1,2]-domination in arbitrary vertex-transitive graphs.
For large n the closed-form values allow immediate computation without search.

Load-bearing premise

That exhaustive case analysis or explicit constructions for all n produce the claimed minimum sizes without overlooked exceptions or n-dependent anomalies.

What would settle it

An explicit n together with a [1,2]-dominating set in P(n,2) whose size is strictly smaller than the value stated by the paper.

Figures

Figures reproduced from arXiv: 1906.11966 by Fairouz Beggas, Hamamache Kheddouci, Mohammed Haddad, Volker Turau.

**Figure 1.** Figure 1: The minimum [1, 2]-domination sets of the generalized Petersen graphs P(5, 2) and P(6, 2) and the minimum [1, 2]-total dominating set for P(5, 2). Definition 2. A block b of P(n, 2) is the subgraph induced by the six vertices {vi−1, vi , vi+1, ui−1, ui , ui+1} for any i ∈ {0, . . . n − 1}. A block is called positive if two of the indices of {vi−1, vi , vi+1} are odd, otherwise it is called negative [PITH_… view at source ↗

**Figure 2.** Figure 2: shows a series of blocks of P(n, 2). The second block is positive while the other two are negative. Note that blocks can overlap. If b is a block, the block to the left is denoted by b − and that to the right by b +. b − b b+ ui−4 ui−3 ui−2 ui−1 ui ui+1 ui+2 ui+3 ui+4 vi−4 vi−3 vi−2 vi−1 vi vi+1 vi+2 vi+3 vi+4 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** Figure 3: f(n) is an upper bound of γ[1,2](P(n, 2)) for all n > 12 Lemma 6. Let x be any solution of Eq. (3.1). Then xi ≤ 1 for i = 0, . . . , n − 1. Proof. Let x be any solution of Eq. (3.1) such that xi = 2 for some i. Without loss of generality i = 0. By Lemma 5 there exist a solution which coincides with x except x1 = x2 = 0 and x3 = 2. Repeatedly applying Lemma 5 proves that there exits a [PITH_FULL_IMAGE:figu… view at source ↗

**Figure 4.** Figure 4: The partition of P(n, 2) into n pairs. solution ˆx of Eq. (3.1) with ˆxk = 2 and ˆxk+1 = ˆxk+2 = 0 for k = 0, 1, . . . , bn/3c. If n ≡ 0 [3] then Pn−1 i=0 xˆi = 2n/3 = f(n), which is impossible. Suppose n ≡ 1 [3]. Then ˆxn−1 = 2 otherwise the second constraint for i = n − 2 would be violated. This leads to the contradiction Pn−1 i=0 xˆi = 2bn/3c + 2 ≥ f(n). Hence, n ≡ 2 [3]. Then ˆxn−2 = 2 otherwise the se… view at source ↗

**Figure 5.** Figure 5: If v0, u1 ∈ S then vertices depicted in red must also be in S. Case 2. u0, v1 ∈ S (see [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗

**Figure 6.** Figure 6: If u0, v1 ∈ S then vertices depicted in red must also be in S. Case 3. u0, u1 ∈ S. The same reasoning as above leads to the situation depicted in [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗

**Figure 7.** Figure 7: If u0, u1 ∈ S then vertices depicted in red must also be in S. Case 4. v0, v1 ∈ S. The same reasoning as above leads to the situation depicted in [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗

**Figure 8.** Figure 8: If v0, v1 ∈ S then vertices depicted in red must also be in S. This concludes the proof of Theorem 1 for the case B1(S) = ∅. 3.2. Case B1(S) 6= ∅ The following simple observation is based on the fact that the central vertex of a block b can only be dominated by a vertex within b. Lemma 9. Any positive block b ∈ B1(S) corresponds to one of the four blocks shown in [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗

**Figure 9.** Figure 9: The four types of positive blocks with γS(b) = 1. Proof. In order to dominate vi−1 and vi+1 from block b, vertices vi−3 from block b − and vi+3 from b + need to be in S. The idea is to move some dominating nodes such that block b is not no longer of type B and no new block of type B emerges while S is still [1, 2]-dominating and the cardinality of S remains. The proof is divided into four cases, considerin… view at source ↗

**Figure 10.** Figure 10: Maximal components induced by P2 and P3 and their neighbors [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗

**Figure 11.** Figure 11: Impossible partitionings. 5. Conclusion Generalized Petersen graphs are very important structures in computer science and communication techniques since their particular structures and interesting properties. In this paper, we considered a variant of the dominating set problem, called the [1, 2]-dominating set problem. We studied this problem in generalized Petersen graphs P(n, k) for k = 2. We gave the… view at source ↗

**Figure 12.** Figure 12: The construction of γt[1,2](P(n, 2)) for n ≡ 1[6]. domination numbers of P(n, k) with k ≥ 3. References [1] Arash Behzad, Mehdi Behzad, and Cheryl Praeger. On the domination number of the generalized petersen graphs. Discrete Mathematics, 308(4):603 – 610, 2008. [2] Jianxiang Cao, Weiguo Lin, and Minyong Shi. Total domination number of generalized petersen graphs. Intelligent Information Management, 1(1)… view at source ↗

read the original abstract

A vertex subset $S$ of a graph $G=(V,E)$ is a $[1,2]$-dominating set if each vertex of $V\backslash S$ is adjacent to either one or two vertices in $S$. The minimum cardinality of a $[1,2]$-dominating set of $G$, denoted by $\gamma_{[1,2]}(G)$, is called the $[1,2]$-domination number of $G$. In this paper the $[1,2]$-domination and the $[1,2]$-total domination numbers of the generalized Petersen graphs $P(n,2)$ are determined.

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.

Desk Editor's Note private letter to a colleague

The paper pins down exact values for both the [1,2]-domination number and [1,2]-total domination number on P(n,2) for every n via case analysis.

read the letter

The paper determines the [1,2]-domination number and the [1,2]-total domination number for the generalized Petersen graphs P(n,2). This extends earlier exact results on ordinary domination and total domination for the same family to the variant where every vertex outside the set has one or two neighbors inside it. They achieve this with explicit constructions for the upper bound and matching lower bounds from exhaustive local configuration analysis around the outer cycle, inner cycle, and spokes, split by n modulo a small integer plus direct checks for small n. The structure of P(n,2) makes that partitioning feasible, and the work supplies the formulas that follow from the cases. That is the actual contribution: closed expressions rather than bounds. The methods are the standard ones for this corner of graph theory, and the citation pattern to prior domination results on Petersen graphs is appropriate. The soft spot is the completeness of the case split itself. If any local configuration is overlooked in one congruence class, or if the counting argument for the lower bound has an edge case that only appears for certain n, the claimed exact value would not hold. The stress-test note flags exactly this risk, and it is the part that needs the most scrutiny in review. Nothing else in the approach looks fragile. This is for people who track exact domination parameters on specific infinite families. A reader already working on generalized Petersen graphs or [1,2]-domination will find the numbers useful and the proofs checkable. It is narrow enough that most groups would skip it, but the result is a clean determination rather than an incremental bound. Send it to peer review; the central claim is precise enough to be worth referee time even if revisions are needed on the case coverage.

Referee Report

2 major / 2 minor

Summary. The paper determines the exact values of the [1,2]-domination number γ_{[1,2]}(P(n,2)) and the [1,2]-total domination number for the generalized Petersen graphs P(n,2) with n ≥ 3. It supplies explicit formulas (partitioned by n mod k for small k) together with matching upper-bound constructions and lower-bound arguments based on exhaustive local case analysis around the outer cycle, inner cycle, and spokes.

Significance. Exact determination of these parameters on the infinite family P(n,2) supplies closed-form expressions for an important class of 3-regular vertex-transitive graphs. If the case analysis is complete, the result supplies a concrete benchmark for [1,2]-domination theory and enables immediate computation for any concrete n.

major comments (2)

[§3] §3 (lower-bound case analysis): the partition into congruence classes is stated but the proof does not explicitly enumerate the possible neighborhoods of a vertex on the outer cycle when exactly one spoke is used; it is unclear whether the counting argument still yields the claimed lower bound when n ≡ 2 mod 4 and the inner-cycle vertices are alternately dominated.
[Theorem 4.1] Theorem 4.1 (total-domination formula): the claimed value for n ≡ 1 mod 3 appears to rely on a periodic pattern that is verified only up to n=20; no separate verification or additional case is supplied for the boundary n=25, leaving open whether an exceptional configuration exists.

minor comments (2)

[§2] Notation: the symbol γ_{[1,2]}^t is introduced without an explicit definition sentence; it should be defined immediately after the ordinary [1,2]-domination number.
[Figure 2] Figure 2: the labeling of vertices in the drawing of P(7,2) is inconsistent with the vertex ordering used in the case analysis of §3.2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the careful reading and the specific comments that highlight opportunities to improve the clarity of the case analysis. We address each major comment point by point below.

read point-by-point responses

Referee: [§3] §3 (lower-bound case analysis): the partition into congruence classes is stated but the proof does not explicitly enumerate the possible neighborhoods of a vertex on the outer cycle when exactly one spoke is used; it is unclear whether the counting argument still yields the claimed lower bound when n ≡ 2 mod 4 and the inner-cycle vertices are alternately dominated.

Authors: We thank the referee for noting this point of potential ambiguity. The lower-bound argument in §3 relies on exhaustive enumeration of local configurations around outer-cycle vertices, spokes, and inner-cycle vertices; the cases with exactly one spoke are subsumed in the congruence-class partitions and the counting of dominated vertices. The n ≡ 2 mod 4 situation with alternating inner-cycle domination is covered by the same counting, as the spoke constraint forces additional outer-cycle coverage that preserves the bound. Nevertheless, to make the enumeration fully explicit we will insert a short additional lemma listing the one-spoke neighborhoods and verifying the bound in each subcase, including n ≡ 2 mod 4. revision: yes
Referee: [Theorem 4.1] Theorem 4.1 (total-domination formula): the claimed value for n ≡ 1 mod 3 appears to rely on a periodic pattern that is verified only up to n=20; no separate verification or additional case is supplied for the boundary n=25, leaving open whether an exceptional configuration exists.

Authors: The formula in Theorem 4.1 for n ≡ 1 mod 3 is obtained from a uniform periodic construction together with a matching lower bound that follows from the same exhaustive local analysis used throughout the paper; the argument is not limited to computational checks up to n=20. The small-n verifications are presented only as illustrations. To address the referee’s concern we will add an explicit remark confirming the configuration for n=25 (and, if space permits, one larger example) so that readers see the pattern continues without exception. revision: partial

Circularity Check

0 steps flagged

No circularity: direct combinatorial determination via constructions and case analysis

full rationale

The paper determines γ_{[1,2]}(P(n,2)) and the total variant by providing explicit constructions (upper bounds) and matching lower bounds obtained from exhaustive local case analysis on the outer cycle, inner cycle, and spokes of P(n,2), partitioned by n mod k. No equations fit parameters to subsets of results and then rename those fits as predictions; no self-citation supplies a load-bearing uniqueness theorem or ansatz; the result is not defined in terms of itself. The derivation chain consists of independent graph-theoretic arguments that stand on their own combinatorial content rather than reducing to prior fitted values or author-overlapping citations.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no free parameters, axioms, or invented entities can be identified from the given text.

pith-pipeline@v0.9.0 · 5643 in / 957 out tokens · 23782 ms · 2026-05-25T13:23:21.181001+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1. γ[1,2](P(n,2)) = 2n/3 if n≡0,3[6]; 2⌊n/3⌋+1 if n≡1[6]; 2⌊n/3⌋+2 otherwise (n≥5). Proof splits on B1(S)=∅ vs nonempty, using pair inequalities and type-A/B/C/D block reductions.
IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Definition 2. Block b induced by {vi−1,vi,vi+1,ui−1,ui,ui+1}; positive/negative by parity count; Bi(S) counts blocks with exactly i members of S.

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]

On the domination number of the generalized petersen graphs

Arash Behzad, Mehdi Behzad, and Cheryl Praeger. On the domination number of the generalized petersen graphs. Discrete Mathematics, 308(4):603 – 610, 2008

work page 2008
[2]

Total domination number of general- ized petersen graphs

Jianxiang Cao, Weiguo Lin, and Minyong Shi. Total domination number of general- ized petersen graphs. Intelligent Information Management , 1(1):14–17, 2009

work page 2009
[3]

Haynes, Stephen T

Mustapha Chellali, Teresa W. Haynes, Stephen T. Hedetniemi, and Alice McRae. [1,2]-sets in graphs. Discrete Applied Mathematics , 161(18):2885 – 2893, 2013

work page 2013
[4]

Graph Theory, 4th Edition , volume 173 of Graduate Texts in Math- ematics

Reinhard Diestel. Graph Theory, 4th Edition , volume 173 of Graduate Texts in Math- ematics. Springer, 2012

work page 2012
[5]

Javad Ebrahimi, Naﬁseh Jahanbakht, and E

B. Javad Ebrahimi, Naﬁseh Jahanbakht, and E. Mahmoodian. Vertex domination of generalized Petersen graphs. Discrete Mathematics, 309(13):4355 – 4361, 2009

work page 2009
[6]

On the domination number of gen- eralized Petersen graphs P(n,2)

Xueliang Fu, Yuansheng Yang, and Baoqi Jiang. On the domination number of gen- eralized Petersen graphs P(n,2). Discrete Mathematics, 309(8):2445 – 2451, 2009

work page 2009
[7]

Haynes, S.T

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, 1998

work page 1998
[8]

On the Signed Total Domina- tion Number of Generalized Petersen Graphs P(n,2)

Wen-Sheng Li, Hua-Ming Xing, and Moo Young Sohn. On the Signed Total Domina- tion Number of Generalized Petersen Graphs P(n,2). Bulletin of the Korean Mathe- matical Society, 60(6):2021 – 2026, 2013

work page 2021
[9]

A theorem on Tait colorings with an application to generalized Pe- tersen graphs

Mark Watkins. A theorem on Tait colorings with an application to generalized Pe- tersen graphs. J. of Combinatorial Theory , 6(2):152 – 164, 1969

work page 1969
[10]

The exact domination number of the generalized petersen graphs

Hong Yan, Liying Kang, and Guangjun Xu. The exact domination number of the generalized petersen graphs. Discrete Mathematics, 309(8):2596 – 2607, 2009

work page 2009
[11]

[1,2]-domination in graphs

Xiaojing Yang and Baoyindureng Wu. [1,2]-domination in graphs. Discrete Applied Mathematics, 175:79 – 86, 2014

work page 2014
[12]

Domination in generalized petersen graphs

Bohdan Zelinka. Domination in generalized petersen graphs. Czechoslovak Mathemat- ical Journal, 52(1):11–16, 2002

work page 2002

[1] [1]

On the domination number of the generalized petersen graphs

Arash Behzad, Mehdi Behzad, and Cheryl Praeger. On the domination number of the generalized petersen graphs. Discrete Mathematics, 308(4):603 – 610, 2008

work page 2008

[2] [2]

Total domination number of general- ized petersen graphs

Jianxiang Cao, Weiguo Lin, and Minyong Shi. Total domination number of general- ized petersen graphs. Intelligent Information Management , 1(1):14–17, 2009

work page 2009

[3] [3]

Haynes, Stephen T

Mustapha Chellali, Teresa W. Haynes, Stephen T. Hedetniemi, and Alice McRae. [1,2]-sets in graphs. Discrete Applied Mathematics , 161(18):2885 – 2893, 2013

work page 2013

[4] [4]

Graph Theory, 4th Edition , volume 173 of Graduate Texts in Math- ematics

Reinhard Diestel. Graph Theory, 4th Edition , volume 173 of Graduate Texts in Math- ematics. Springer, 2012

work page 2012

[5] [5]

Javad Ebrahimi, Naﬁseh Jahanbakht, and E

B. Javad Ebrahimi, Naﬁseh Jahanbakht, and E. Mahmoodian. Vertex domination of generalized Petersen graphs. Discrete Mathematics, 309(13):4355 – 4361, 2009

work page 2009

[6] [6]

On the domination number of gen- eralized Petersen graphs P(n,2)

Xueliang Fu, Yuansheng Yang, and Baoqi Jiang. On the domination number of gen- eralized Petersen graphs P(n,2). Discrete Mathematics, 309(8):2445 – 2451, 2009

work page 2009

[7] [7]

Haynes, S.T

T.W. Haynes, S.T. Hedetniemi, and P.J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, 1998

work page 1998

[8] [8]

On the Signed Total Domina- tion Number of Generalized Petersen Graphs P(n,2)

Wen-Sheng Li, Hua-Ming Xing, and Moo Young Sohn. On the Signed Total Domina- tion Number of Generalized Petersen Graphs P(n,2). Bulletin of the Korean Mathe- matical Society, 60(6):2021 – 2026, 2013

work page 2021

[9] [9]

A theorem on Tait colorings with an application to generalized Pe- tersen graphs

Mark Watkins. A theorem on Tait colorings with an application to generalized Pe- tersen graphs. J. of Combinatorial Theory , 6(2):152 – 164, 1969

work page 1969

[10] [10]

The exact domination number of the generalized petersen graphs

Hong Yan, Liying Kang, and Guangjun Xu. The exact domination number of the generalized petersen graphs. Discrete Mathematics, 309(8):2596 – 2607, 2009

work page 2009

[11] [11]

[1,2]-domination in graphs

Xiaojing Yang and Baoyindureng Wu. [1,2]-domination in graphs. Discrete Applied Mathematics, 175:79 – 86, 2014

work page 2014

[12] [12]

Domination in generalized petersen graphs

Bohdan Zelinka. Domination in generalized petersen graphs. Czechoslovak Mathemat- ical Journal, 52(1):11–16, 2002

work page 2002