Upper paired domination in graphs
| Autor: | Huiqin Jiang, Pu Wu, Jingzhong Zhang, Yongsheng Rao |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | AIMS Mathematics, Vol 7, Iss 1, Pp 1185-1197 (2022) |
| Druh dokumentu: | article |
| ISSN: | 2473-6988 45434409 |
| DOI: | 10.3934/math.2022069?viewType=HTML |
| Popis: | 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 $. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|