Paired Domination Number of Generalized Petersen Graphs $P(n,2)$

Abstract

Let $G=(V,E)$ be a simple graph. A paired-dominating set of a graph $G$ is a dominating set whose induced subgraph contains a perfect matching. The paired domination number of a graph $G$, denoted by ${\gamma }_p(G)$, is the minimum cardinality of a paired-dominating set in $G$. In this paper, we study the paired domination number of generalized Petersen graphs $P(n,2)$ and prove that for any integer $n\ge 6$, ${\gamma }_p(P(n,2))=2\lfloor \frac{n}{3}\rfloor +n(\mathrm{mod}3)$.