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 ∪ E ) \ D is a neighbor of some elements in D. The mixed domination number of G, denoted by $$\gamma _{\textrm{md}}(G)$$ γ md ( G ) , is the minimum size among all mixed dominating sets of G. For natural numbers n and k, where $$n > 2k$$ n > 2 k , 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 , … , v n - 1 } ∪ { u 0 , u 1 , … , u n - 1 } and edges $$\cup _{0 \le i \le n-1} \{v_{i} v_{i+1}, v_iu_i, u_iu_{i+k}\}$$ ∪ 0 ≤ i ≤ 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 ∈ { 1 , 2 } . Moreover, we establish some upper bound on mixed domination number for other generalized Petersen graphs.