Pairwise and variance balanced n-ary block designs

Abstract

The paired domination subdivision number ${\text{sd}}_{pr}(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 \textit{paired domination multisubdivision number} of a nonempty graph $G$, denoted by ${\text{msd}}_{pr}(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 ${\text{msd}}_{pr}(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 characterization of all trees with paired domination multisubdivision number equal to 4.