Roman domination number of Generalized Petersen Graphs \(P(n, 2)\)

Abstract

A \({Roman \;domination \;function}\) on a graph \(G = (V, E)\) is a function \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) with \(f(u) = 0\) is adjacent to at least one vertex \(v\) with \(f(v) = 2\). The \({weight}\) of a Roman domination function \(f\) is the value \(f(V(G)) = \sum_{u \in V(G)} f(u)\). The minimum weight of a Roman dominating function on a graph \(G\) is called the \({Roman \;domination \;number}\) of \(G\), denoted by \(\gamma_R(G)\). In this paper, we study the Roman domination number of generalized Petersen graphs \(P(n, 2)\) and prove that \(\gamma_R(P(n, 2)) = \left\lceil \frac{8n}{7} \right\rceil (n\geq5)\).