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) \geq 3 \). That is, \(S\) is a packing if and only if for any vertex \(v \in V(G)\), \(|N[v] \cap S| \leq 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)) = \left\lfloor \frac{n}{7} \right\rfloor + \left\lceil \frac{n+1}{7} \right\rceil + \left\lfloor \frac{n+4}{7} \right\rfloor\) (\(n \geq 5\)).