Independent domination subdivision in graphs (Q2045365)

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\) with order \(|V(G)|\) and size \(|E(G)|\). A set \(D \subseteq V(G)\) is a dominating set of \(G\) if each vertex not in \(D\) is adjacent to at least one vertex of \(D\) in \(G\), and the domination number \(\gamma(G)\) of \(G\) is the minimum cardinality among all dominating sets of \(G\). A set \(Q \subseteq V(G)\) is an independent set of \(G\) if no two distinct vertices in \(Q\) are adjacent in \(G\). The independent domination number \(i(G)\) of \(G\) is the minimum cardinality among all vertex subsets \(S\) of \(G\) such that \(S\) is both a dominating set and an independent set of \(G\). Let \(G^\ast\) be a graph obtained from \(G\) by subdividing each edge at most once. The domination subdivision number \(\mathrm{sd}_{\gamma}(G)\) of \(G\) is \(\min\{|V(G^\ast)|-|V(G)|: \gamma(G^\ast)>\gamma(G)\}\), and the independent domination subdivision number \(\mathrm{sd}_i(G)\) of \(G\) is \(\min\{|V(G^\ast)|-|V(G)|: i(G^\ast)>i(G)\}\). In this paper, the authors study the independent domination subdivision number of connected graphs. Let \(\Delta(G)\) and \(\delta(G)\) respectively denote the maximum and the minimum degree of \(G\). For any connected graph \(G\) of order at least three, the authors show that \(\mathrm{sd}_i(G)\le \Delta(G) \cdot i(G)\). They also show that \(\mathrm{sd}_i(K_{t,t})= 3t-2\) for \(t\ge 4\), where \(K_{a,b}\) denotes the complete bi-partite graph with partite sets of size \(a\) and \(b\). This, together with the known result \(\mathrm{sd}_{\gamma}(G)\le \delta(G)+\Delta(G)-1\), implies that \(\mathrm{sd}_i(K_{t,t})-\mathrm{sd}_{\gamma}(K_{t,t})\) can be arbitrarily large. The authors also provide a realization result on the independent domination subdivision number of block graphs. Moreover, for any tree \(T\) of order at least three, they show that \(1\le \mathrm{sd}_i(T)\le3\) and they characterize trees \(T\) satisfying \(\mathrm{sd}_i(T)=1\).