Paired domination subdivision and multisubdivision numbers of graphs

Abstract

The paired domination subdivision number $s{d}_p(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of $G$. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination multisubdivision number of a nonempty graph $G$, denoted by $ms{d}_p(G)$, as the minimum positive integer $k$ such that there exists an edge which must be subdivided $k$ times to increase the paired domination number of $G$. We show that $ms{d}_p(G)\le 4$ for any graph $G$ with at least one edge. We also determine paired domination multisubdivision numbers for some classes of graphs. Moreover, we give a constructive characterizations of all trees with paired domination multisubdivision number equal to 4.