Independent dominating set

General bounds

Berge established basic bounds in terms of the order ${\displaystyle n}$ and maximum degree ${\displaystyle \Delta }$ of a graph:^[7]

${\displaystyle \left\lceil {\frac {n}{1+\Delta }}\right\rceil \leq i(G)\leq n-\Delta }$

For graphs without isolated vertices:^[8]

${\displaystyle i(G)\leq n+2-2{\sqrt {n}}}$

and this bound is sharp. For a graph with minimum degree at least ${\displaystyle \delta }$:^[9]

${\displaystyle i(G)\leq n+2\delta -2{\sqrt {\delta n}}}$

confirming an earlier conjecture of Favaron.^[8]

Graph families

For claw-free graphs:^[10]

${\displaystyle i(G)=\gamma (G)}$

More generally, for ${\displaystyle K_{1,k}}$-free (star-free) graphs where ${\displaystyle k\geq 3}$:^[11]

${\displaystyle i(G)\leq (k-2)\gamma (G)-(k-3)}$

For any bipartite graph without isolated vertices on ${\displaystyle n}$ vertices:^[1]

${\displaystyle i(G)\leq n/2}$

For trees, if a tree has ${\displaystyle n}$ vertices and ${\displaystyle \ell }$ leaves:^[12]

${\displaystyle i(G)\leq (n+\ell )/3}$

If ${\displaystyle G}$ is an ${\displaystyle r}$-regular graph on ${\displaystyle n}$ vertices with no isolated vertex, then:^[13]

${\displaystyle i(G)\leq \alpha (G)\leq n/2}$

For connected cubic graphs other than ${\displaystyle K_{3,3}}$:^[14]

${\displaystyle i(G)\leq 2n/5}$

It has been conjectured that the bound can be improved to ${\displaystyle 3n/8}$ for all connected cubic graphs of order more than 10.^[1]

Regarding the ratio between domination and independent domination in connected cubic graphs other than ${\displaystyle K_{3,3}}$:^[15]

${\displaystyle i(G)/\gamma (G)\leq 4/3}$

For any planar graph on ${\displaystyle n}$ vertices:^[16]

${\displaystyle i(G)\leq 3n/4-2}$

For planar graphs of diameter 2, the bound can be improved:^[16]

${\displaystyle i(G)\leq \lceil n/3\rceil }$

Relation to line graphs and edge domination

For any graph ${\displaystyle G}$, its line graph ${\displaystyle L(G)}$ is claw-free, and hence a minimum maximal independent set in ${\displaystyle L(G)}$ is also a minimum dominating set in ${\displaystyle L(G)}$. An independent set in ${\displaystyle L(G)}$ corresponds to a matching in ${\displaystyle G}$, and a dominating set in ${\displaystyle L(G)}$ corresponds to an edge dominating set in ${\displaystyle G}$. Therefore a minimum maximal matching has the same size as a minimum edge dominating set.

Relation to other domination parameters

Because the minimum is taken over fewer sets (only the independent dominating sets are considered), ${\displaystyle \gamma (G)\leq i(G)}$ for all graphs ${\displaystyle G}$. Similarly, since every maximal independent set is an independent set, ${\displaystyle i(G)\leq \alpha (G)}$, where ${\displaystyle \alpha (G)}$ is the independence number. Furthermore, since every maximal independent set is a minimal dominating set, ${\displaystyle \alpha (G)\leq \Gamma (G)}$, where ${\displaystyle \Gamma (G)}$ is the upper domination number (the maximum size of a minimal dominating set). This yields the domination chain:^[17]

${\displaystyle \gamma (G)\leq i(G)\leq \alpha (G)\leq \Gamma (G).}$

The inequality can be strict; there are graphs ${\displaystyle G}$ for which ${\displaystyle \gamma (G)<i(G)}$. For example, let ${\displaystyle G}$ be the double star graph consisting of vertices ${\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}$, where ${\displaystyle p,q>1}$. The edges of ${\displaystyle G}$ are defined as follows: each ${\displaystyle x_{i}}$ is adjacent to ${\displaystyle a}$, ${\displaystyle a}$ is adjacent to ${\displaystyle b}$, and ${\displaystyle b}$ is adjacent to each ${\displaystyle y_{j}}$. Then ${\displaystyle \gamma (G)=2}$ since ${\displaystyle \{a,b\}}$ is a smallest dominating set. If ${\displaystyle p\leq q}$, then ${\displaystyle i(G)=p+1}$ since ${\displaystyle \{x_{1},\ldots ,x_{p},b\}}$ is a smallest dominating set that is also independent (it is a smallest maximal independent set).

However, the bounds ${\displaystyle \gamma (G)\leq i(G)\leq \alpha (G)}$ are simultaneously sharp for the corona ${\displaystyle H\circ K_{1}}$ of any graph ${\displaystyle H}$, which satisfies ${\displaystyle \gamma (G)=i(G)=\alpha (G)=|V(H)|}$.^[1]

Cockayne and Mynhardt characterized which sequences of values are achievable:^[18] A sequence ${\displaystyle (s_{1},s_{2},s_{3},s_{4})}$ of integers is realizable as ${\displaystyle (\gamma (G),i(G),\alpha (G),\Gamma (G))}$ for some graph ${\displaystyle G}$ if and only if ${\displaystyle 1\leq s_{1}\leq s_{2}\leq s_{3}\leq s_{4}}$, ${\displaystyle s_{1}=1}$ implies ${\displaystyle s_{2}=1}$, and ${\displaystyle s_{3}=1}$ implies ${\displaystyle s_{4}=1}$.