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.
展开▼
