Domination and Independent Domination Numbers of Graphs

Abstract

Let $X$ be a graph and let $\alpha (X)$ and ${\alpha }^{\prime }(X)$ denote the domination number and independent domination number of $X$, respectively. We show that for every triple $(m,k,n)$, $m\ge 5$, $2\le k\le m$, $n>1$, there exist $m$-regular $k$-connected graphs $X$ with ${\alpha }^{\prime }(X)–\alpha (X)>n$. The same also holds for $m=4$ and $k\in \{2,4\}$.