Repozytorium publikacji - Politechnika Gdańska

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$.

Autorzy

• Ammar Babikir,
• dr inż. Magda Dettlaff link otwiera się w nowej karcie ,
• Michael A. Henning,
• dr inż. Magdalena Lemańska link otwiera się w nowej karcie