## Domination subdivision numbers in graphs.(English)Zbl 1071.05057

A set $$S$$ of vertices of a graph $$G$$ is a dominating set if each vertex outside $$S$$ has a neighbor in $$S$$. The domination number $$\gamma(G)$$ of $$G$$ is the minimum cardinality of a dominating set of $$G$$. An edge $$uv$$ in $$G$$ is subdivided if the edge $$uv$$ is deleted, but a new vertex $$x$$ is added, along with two new edges $$xu$$ and $$xv$$. The domination subdivision number $$sd_\gamma(G)$$ of a graph $$G$$ is the minimum number of edges in $$G$$ that must be subdivided, each at most once, in order to increase the domination number. The authors prove several upper bounds for $$sd_\gamma(G)$$ in terms of vertex degrees, and discuss the conjecture $$sd_\gamma(G)\leq 4$$ for any graph $$G$$ with at least 3 vertices, respectively, $$sd_\gamma(G)\leq \delta(G)+1$$ for any graph $$G$$ with minmum degree $$\delta(G)\geq 2$$. In particular, the authors point out several graph classes in which the conjectures hold.

### MSC:

 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)