
<abstract><p>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 $ <sup>[<xref ref-type="bibr" rid="b11">11</xref>]</sup>. In this paper, we show that $ Upper $-$ PDS $ is APX-complete for bipartite graphs with $ \Delta = 3 $.</p></abstract>
Combinatorial Optimization and Complexity Theory, Limits and Structures in Graph Theory, Mathematical analysis, apx-completeness, Graph, Upper and lower bounds, Graph Limits, Dominating set, QA1-939, FOS: Mathematics, Discrete Mathematics and Combinatorics, Bipartite graph, Induced subgraph, upper paired domination, Graph Algorithms, Discrete mathematics, Vertex (graph theory), Computational Theory and Mathematics, Combinatorics, Graph Theory, Computer Science, Physical Sciences, Mathematics, Graph Theory and Algorithms
Combinatorial Optimization and Complexity Theory, Limits and Structures in Graph Theory, Mathematical analysis, apx-completeness, Graph, Upper and lower bounds, Graph Limits, Dominating set, QA1-939, FOS: Mathematics, Discrete Mathematics and Combinatorics, Bipartite graph, Induced subgraph, upper paired domination, Graph Algorithms, Discrete mathematics, Vertex (graph theory), Computational Theory and Mathematics, Combinatorics, Graph Theory, Computer Science, Physical Sciences, Mathematics, Graph Theory and Algorithms
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
