On the Domination Number of Generalized Petersen Graphs \(P(ck, k)\)

Abstract

Let \(G = (V(G), E(G))\) be a simple, connected, and undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). A set \(S \subseteq V(G)\) is a \emph{dominating set} if for each \(v \in V(G)\), either \(v \in S\) or \(v\) is adjacent to some \(w \in S\). That is, \(S\) is a dominating set if and only if \(N[S] = V(G)\). The \emph{domination number} \(\gamma(G)\) is the minimum cardinality of minimal dominating sets. In this paper, we provide an improved upper bound on the domination number of generalized Petersen graphs \(P(c,k)\) for \(c \geq 3\) and \(k \geq 3\). We also prove that \(\gamma(P(4k,k)) = 2k + 1\) for even \(k\), \(\gamma(P(5k, k)) = 3k\) for all \(k \geq 1\), and \(\gamma(P(6k,k)) = \left\lceil \frac{10k}{3} \right\rceil\) for \(k \geq 1\) and \(k \neq 2\).