@article{Jiang2022, 
author = {Huiqin Jiang and Pu Wu and Jingzhong Zhang and Yongsheng Rao},
title = {Upper paired domination in graphs},
year = {2022},
journal = {AIMS Mathematics},
volume = {7},
number = {1},
pages = {1185-1197},
keywords = {upper paired domination, APX-completeness},
url = {https://www.sciopen.com/article/10.3934/math.2022069},
doi = {10.3934/math.2022069},
abstract = {A set    P  D  ⊆  V  (  G  ) in a graph    G is a paired dominating set if every vertex    v  ∉  P  D is adjacent to a vertex in    P  D and the subgraph induced by    P  D contains a perfect matching. A paired dominating set    P  D of    G is minimal if there is no proper subset    P      D    ′    ⊂  P  D 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        Γ          p      r        (  G  )-set. Denote by    U  p  p  e  r-   P  D  S the problem of computing a        Γ          p      r        (  G  )-set for a given graph    G. Michael et al. showed the APX-completeness of    U  p  p  e  r-   P  D  S for bipartite graphs with    Δ  =  4 [11]. In this paper, we show that    U  p  p  e  r-   P  D  S is APX-complete for bipartite graphs with    Δ  =  3.}
}