Independent dominating set

A graph with a minimum independent dominating set in red. There are 3 vertices in the set, and therefore the independent domination number $i(G)=3$ (which is greater than the domination number $\gamma (G)=2$).

In graph theory, an independent dominating set for a graph $G=(V,E)$ is a subset $D\subseteq V$ that is both a dominating set and an independent set; equivalently, it is a maximal independent set.

The independent domination number $i(G)$ of a graph $G$ is the size of the smallest independent dominating set (equivalently, the smallest maximal independent set). The notation $i(G)$ was introduced by Cockayne and Hedetniemi.

History

The concept of an independent dominating set arose from chess problems. In 1862, de Jaenisch posed the problem of finding the minimum number of mutually non-attacking queens that can be placed on a chessboard so that every square is attacked by at least one queen. Modelling the chessboard as a queen's graph $G$, this minimum is the independent domination number $i(G)$. For the standard 8×8 queens graph, $\alpha (G)=8$, $i(G)=7$, and $\gamma (G)=5$.

The theory of independent domination was formalized by Berge and Ore in 1962. Berge observed that an independent set is maximal independent if and only if it is dominating, and that every maximal independent set is a minimal dominating set.

Bounds

General bounds

Berge established basic bounds in terms of the order $n$ and maximum degree $\mathrm{\Delta }$ of a graph:

$\lceil \frac{n}{1+\mathrm{\Delta }}\rceil \le i(G)\le n-\mathrm{\Delta }$

For graphs without isolated vertices:

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

and this bound is sharp. For a graph with minimum degree at least $\delta$:

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

confirming an earlier conjecture of Favaron.

Graph families

For claw-free graphs:

$i(G)=\gamma (G)$

More generally, for $K_{1,k}$-free (star-free) graphs where $k\ge 3$:

$i(G)\le (k-2)\gamma (G)-(k-3)$

For any bipartite graph without isolated vertices on $n$ vertices:

$i(G)\le n/2$

For trees, if a tree has $n$ vertices and $\ell$ leaves:

$i(G)\le (n+\ell )/3$

If $G$ is an $r$-regular graph on $n$ vertices with no isolated vertex, then:

$i(G)\le \alpha (G)\le n/2$

For connected cubic graphs other than $K_{3,3}$:

$i(G)\le 2n/5$

It has been conjectured that the bound can be improved to $3n/8$ for all connected cubic graphs of order more than 10.

Regarding the ratio between domination and independent domination in connected cubic graphs other than $K_{3,3}$:

$i(G)/\gamma (G)\le 4/3$

For any planar graph on $n$ vertices:

$i(G)\le 3n/4-2$

For planar graphs of diameter 2, the bound can be improved:

$i(G)\le \lceil n/3\rceil$

Relation to line graphs and edge domination

For any graph $G$, its line graph $L(G)$ is claw-free, and hence a minimum maximal independent set in $L(G)$ is also a minimum dominating set in $L(G)$. An independent set in $L(G)$ corresponds to a matching in $G$, and a dominating set in $L(G)$ corresponds to an edge dominating set in $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), $\gamma (G)\le i(G)$ for all graphs $G$. Similarly, since every maximal independent set is an independent set, $i(G)\le \alpha (G)$, where $\alpha (G)$ is the independence number. Furthermore, since every maximal independent set is a minimal dominating set, $\alpha (G)\le \mathrm{\Gamma }(G)$, where $\mathrm{\Gamma }(G)$ is the upper domination number (the maximum size of a minimal dominating set). This yields the domination chain:

$\gamma (G)\le i(G)\le \alpha (G)\le \mathrm{\Gamma }(G).$

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

However, the bounds $\gamma (G)\le i(G)\le \alpha (G)$ are simultaneously sharp for the corona $H\circ K_1$ of any graph $H$, which satisfies $\gamma (G)=i(G)=\alpha (G)=|V(H)|$.

Cockayne and Mynhardt characterized which sequences of values are achievable: A sequence $(s_1,s_2,s_3,s_4)$ of integers is realizable as $(\gamma (G),i(G),\alpha (G),\mathrm{\Gamma }(G))$ for some graph $G$ if and only if $1\le s_1\le s_2\le s_3\le s_4$, $s_1=1$ implies $s_2=1$, and $s_3=1$ implies $s_4=1$.

Computational complexity

Determining whether $i(G)\le k$ for a given graph $G$ and integer $k$ is NP-complete in general, and remains NP-complete even when restricted to bipartite graphs, line graphs, circle graphs, unit disk graphs, or planar cubic graphs. Furthermore, Irving showed that there is no polynomial-time algorithm to approximate the independent domination number within a constant factor unless P = NP.

On the other hand, the independent domination number can be computed in linear time for trees and in polynomial time for chordal graphs and cocomparability graphs.

Domination-perfect graphs

A graph $G$ is called a domination-perfect graph if $\gamma (H)=i(H)$ in every induced subgraph $H$ of $G$. Since an induced subgraph of a claw-free graph is claw-free, it follows that every claw-free graph is also domination-perfect.

By a result of Sumner and Moore, a graph is domination perfect if and only if $\gamma (H)=i(H)$ for every induced subgraph $H$ with $\gamma (H)=2$. Zverovich and Zverovich gave a complete characterization: a graph is domination perfect if and only if it contains none of seventeen specific graphs as an induced subgraph.

Well-covered graphs

A graph is well-covered if $i(G)=\alpha (G)$, that is, every maximal independent set is a maximum independent set. The concept was introduced by Plummer. Ravindra characterized the well-covered bipartite graphs: a connected bipartite graph is well-covered if and only if it contains a perfect matching $M$ such that for every edge $uv\in M$, the subgraph induced by $N[u]\cup N[v]$ is a complete bipartite graph. As a consequence, a tree is well-covered if and only if it is $K_1$ or the corona of a tree.

See also

• Independence dominating set
• Dominating set
• Maximal independent set
• Well-covered graph