Complexity of the paired domination subdivision problem

Abstract

The paired domination subdivision number of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the paired domination number of $G$. In this note, we show that the problem of computing the paired-domination subdivision number is NP-hard for bipartite graphs.