Computing the paired-domination number of a graph has been shown to be NP-complete [1]}.
Chen et al. [2]} further proved that it is NP-complete for bipartite graphs, chordal graphs, and even for split graphs. Thus obtaining tight upper bounds on the paired-domination number of a graph is an interesting problem.
