## Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 691-709 |

Number of pages | 19 |

Journal | Graphs and Combinatorics |

Volume | 37 |

Issue number | 3 |

DOIs | |

Publication status | Published - May 2021 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics