## Domination subdivision numbers.(English)Zbl 1006.05042

A set $$S$$ of vertices of a graph $$G$$ is a dominating set if every vertex of $$V(G)-S$$ is adjacent to some vertex in $$S$$. The domination number $$\gamma(G)$$ is the minimum cardinality of a dominating set of $$G$$, and the domination subdivision number $$\text{sd}_{\gamma}(G)$$ is the minimum number of edges that must be subdivided (each edge in $$G$$ can be subdivided at most once) in order to increase the domination number. In 2000, Arumugam defined the domination subdivision number, and he conjectured that $$1\leq \text{sd}_{\gamma}(G)\leq 3$$ for any graph $$G$$. In this paper, the authors construct a counterexample to this conjecture, and they show that $$\text{sd}_{\gamma}(G)\leq\gamma(G)+1$$ for any graph $$G$$ without isolated vertices. Furthermore, they give constant upper bounds on $$\text{sd}_{\gamma}(G)$$ for several families of graphs. Finally, the authors present some interesting open problems and conjectures.

### MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: