Upper paired domination in graphs

Abstract

A set $ PD\subseteq V(G) $ in a graph $ G $ is a paired dominating set if every vertex $ v\notin PD $ is adjacent to a vertex in $ PD $ and the subgraph induced by $ PD $ contains a perfect matching. A paired dominating set $ PD $ of $ G $ is minimal if there is no proper subset $ PD'\subset PD $ which is a paired dominating set of $ G $. A minimal paired dominating set of maximum cardinality is called an upper paired dominating set, denoted by $ \Gamma_{pr}(G) $-set. Denote by $ Upper $-$ PDS $ the problem of computing a $ \Gamma_{pr}(G) $-set for a given graph $ G $. Michael et al. showed the APX-completeness of $ Upper $-$ PDS $ for bipartite graphs with $ \Delta = 4 $ [11]. In this paper, we show that $ Upper $-$ PDS $ is APX-complete for bipartite graphs with $ \Delta = 3 $.

Keywords

• upper paired domination
• apx-completeness