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.


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