
doi: 10.7151/dmgt.1147
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.
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 15 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
