On the Packing Number of Generalized Petersen Graphs $P(n,2)$

Abstract

Let $G=(V(G),E(G))$ be a graph. A set $S\subseteq V(G)$ is a packing if for any two vertices $u$ and $v$ in $S$ we have $d(u,v)\ge 3$. That is, $S$ is a packing if and only if for any vertex $v\in V(G)$, $|N[v]\cap S|\le 1$. The packing number $\rho (G)$ is the maximum cardinality of a packing in $G$. In this paper, we study the packing number of generalized Petersen graphs $P(n,2)$ and prove that $\rho (P(n,2))=\lfloor \frac{n}{7}\rfloor +\lceil \frac{n+1}{7}\rceil +\lfloor \frac{n+4}{7}\rfloor$ ($n\ge 5$).