Explicit construction of mixed dominating sets in generalized Petersen graphs

A mixed dominating set in a graph \(G=(V,E)\) $G=(V,E)$ is a subset D of vertices and edges of G such that every vertex and edge in \((V\cup E)\setminus D\) $(V\cup E)\backslash D$ is a neighbor of some elements in D. The mixed domination number of G, denoted by \(\gamma _{\textrm{md}}(G)\) ${\gamma }_{\text{md}}(G)$ , is the minimum size among all mixed dominating sets of G. For natural numbers n and k, where \(n > 2k\) $n>2k$ , a generalized Petersen graph P(n, k) is a graph with vertices \( \{v_0, v_1, \ldots , v_{n-1} \}\cup \{u_0, u_1, \ldots , u_{n-1}\}\) $\{v_0,v_1,\dots ,v_{n-1}\}\cup \{u_0,u_1,\dots ,u_{n-1}\}$ and edges \(\cup _{0 \le i \le n-1} \{v_{i} v_{i+1}, v_iu_i, u_iu_{i+k}\}\) ${\cup }_{0\le i\le n-1}\{v_i{v}_{i+1},v_i{u}_i,u_i{u}_{i+k}\}$ where subscripts are modulo n. In this paper, we explicitly construct an optimal mixed dominating set for generalized Petersen graphs P(n, k) for \(k \in \{1, 2\}\) $k\in \{1,2\}$ . Moreover, we establish some upper bound on mixed domination number for other generalized Petersen graphs.