On Mixed Domination in Generalized Petersen Graphs

Abstract

Given a graph $G=(V,E)$, a set $S\subseteq V\cup E$ of vertices and edges is called a mixed dominating set if every vertex and edge that is not included in $S$ happens to be adjacent or incident to a member of $S$. The mixed domination number ${\gamma }_{md}(G)$ of the graph is the size of the smallest mixed dominating set of $G$. We present an explicit method for constructing optimal mixed dominating sets in Petersen graphs $P(n,k)$ for $k\in \{1,2\}$. Our method also provides a new upper bound for other Petersen graphs.