2013/10/04 by Magda Dettlaff, Dettlaff, Magda, Joanna Raczek +3
Mathematics · #05C05 #05C69 #05C99 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C69 #msc:05C99
paper · pdf · doi:10.48550/arxiv.1310.1345
12 pages, 2 figures
arxiv created 2013/10/14 · arxiv updated 2013/10/15
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 \citevel 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 numer of a graph are incomparable in general case, but we show that for trees these two parameters are equal. We also determine domination multisubdivision number for some classes of graphs.