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

Abstract

A $Romandominationfunction$ 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 $Romandominationnumber$ of $G$, denoted by ${\gamma }_R(G)$. In this paper, we study the {\it Roman domination number} of generalized Petersen graphs P(n,2) and prove that ${\gamma }_R(P(n,2))=\lceil \frac{8n}{7}\rceil (n\ge 5)$.

arXiv comment9 pages