Independent Domination Subdivision in Graphs

A set S of vertices in a graph G is a dominating set if every vertex not in S is ad jacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set. The independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. The independent domination subdivision number sd _i(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 independent domination number. We show that for every connected graph G on at least three vertices, the parameter sd _i(G) is well defined and differs significantly from the well-studied domination subdivision number sd _γ(G). For example, if G is a block graph, then sd _γ(G) ≤ 3 , while sd _i(G) can be arbitrary large. Further we show that there exist connected graph G with arbitrarily large maximum degree Δ (G) such that sd _i(G) ≥ 3 Δ (G) - 2 , in contrast to the known result that sd _γ(G) ≤ 2 Δ (G) - 1 always holds. Among other results, we present a simple characterization of trees T with sd _i(T) = 1.