Domination Subdivision Numbers

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number ${\displaystyle s{d}_{\gamma }\left(G\right)}$ 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. Arumugam conjectured that ${\displaystyle 1\le s{d}_{\gamma }\left(G\right)\le 3}$ for any graph G. We give a counterexample to this conjecture. On the other hand, we show that ${\displaystyle s{d}_{\gamma }\left(G\right)\le \gamma \left(G\right)+1}$ for any graph G without isolated vertices, and give constant upper bounds on ${\displaystyle s{d}_{\gamma }\left(G\right)}$ for several families of graphs.