Search
Abstract
A set $S$ of vertices in a graph $G$ is a dominating set if every vertex not in $S$ is adjacent 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 $\sdi(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 $\sdi(G)$ is well defined and differs significantly from the well-studied domination subdivision number $\sdg(G)$. For example, if $G$ is a block graph, then $\sdg(G) \le 3$, while $\sdi(G)$ can be arbitrary large. Further we show that there exist connected graph $G$ with arbitrarily large maximum degree~$\Delta(G)$ such that $\sdi(G) \ge 3 \Delta(G) - 2$, in contrast to the known result that $\sdg(G) \le 2 \Delta(G) - 1$ always holds. Among other results, we present a simple characterization of trees $T$ with $\sdi(T) = 1$.
Citations
-
1
CrossRef
-
0
Web of Science
-
2
Scopus
Authors (4)
-
Ammar Babikir
-
Michael A. Henning
Cite as
Full text
- Publication version
- Accepted or Published Version
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach
- Published in:
-
GRAPHS AND COMBINATORICS
no. 37,
pages 691 - 709,
ISSN: 0911-0119 - Language:
- English
- Publication year:
- 2021
- Bibliographic description:
- Babikir A., Dettlaff M., Henning M. A., Lemańska M.: Independent Domination Subdivision in Graphs// GRAPHS AND COMBINATORICS -Vol. 37,iss. 3 (2021), s.691-709
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s00373-020-02269-3
- Verified by:
- Gdańsk University of Technology
seen 127 times