Explicit construction of mixed dominating sets in generalized Petersen graphs

Abstract

A mixed dominating set in a graph G=(V,E) is a subset D of vertices and edges of G such that every vertex and edge in (V∪E)\D is a neighbor of some elements in D. The mixed domination number of G, denoted by γmd(G), is the minimum size among all mixed dominating sets of G. For natural numbers n and k, where n>2k, a generalized Petersen graph P(n, k) is a graph with vertices {v0,v1,…,vn-1}∪{u0,u1,…,un-1} and edges ∪0≤i≤n-1{vivi+1,viui,uiui+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∈{1,2}. Moreover, we establish some upper bound on mixed domination number for other generalized Petersen graphs. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.