## Abstract

The *domination subdivision number* sd(*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 domination number of *G*. It has been shown [10] that sd(*T*) ≤ 3 for any tree *T*. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the *domination multisubdivision number* of a nonempty graph *G* as a minimum positive integer *k* such that there exists an edge which must be subdivided *k* times to increase the domination number of *G*. We show that msd(*G*) ≤ 3 for any graph *G*. The domination subdivision number and the domination multisubdivision number of a graph are incomparable in general, but we show that for trees these two parameters are equal. We also determine the domination multisubdivision number for some classes of graphs.