Open AccessUpper paired domination in graphs
Author(s) -
Huiqin Jiang,
Pu Wu,
Jingzhong Zhang,
Yongsheng Rao
Publication year - 2021
Publication title -
aims mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.329
H-Index - 15
ISSN - 2473-6988
DOI - 10.3934/math.2022069
Subject(s) - combinatorics , mathematics , dominating set , bipartite graph , vertex (graph theory) , graph , upper and lower bounds , induced subgraph , discrete mathematics , mathematical analysis
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 $.