In graph theory, an independent dominating set for a graph is a subset that is both a dominating set and an independent set; equivalently, it is a maximal independent set.
The independent domination number of a graph is the size of the smallest independent dominating set (equivalently, the smallest maximal independent set). The notation was introduced by Cockayne and Hedetniemi.
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 , this minimum is the independent domination number . For the standard 8ÃÂ8 queens graph, , , and .
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.
Berge established basic bounds in terms of the order and maximum degree of a graph:
For graphs without isolated vertices:
and this bound is sharp. For a graph with minimum degree at least :
confirming an earlier conjecture of Favaron.
For claw-free graphs:
More generally, for -free (star-free) graphs where :
For any bipartite graph without isolated vertices on vertices:
For trees, if a tree has vertices and leaves:
If is an -regular graph on vertices with no isolated vertex, then:
For connected cubic graphs other than :
It has been conjectured that the bound can be improved to for all connected cubic graphs of order more than 10.
Regarding the ratio between domination and independent domination in connected cubic graphs other than :
For any planar graph on vertices:
For planar graphs of diameter 2, the bound can be improved:
For any graph , its line graph is claw-free, and hence a minimum maximal independent set in is also a minimum dominating set in . An independent set in corresponds to a matching in , and a dominating set in corresponds to an edge dominating set in . Therefore a minimum maximal matching has the same size as a minimum edge dominating set.
Because the minimum is taken over fewer sets (only the independent dominating sets are considered), for all graphs . Similarly, since every maximal independent set is an independent set, , where is the independence number. Furthermore, since every maximal independent set is a minimal dominating set, , where is the upper domination number (the maximum size of a minimal dominating set). This yields the domination chain:
The inequality can be strict; there are graphs for which . For example, let be the double star graph consisting of vertices , where . The edges of are defined as follows: each is adjacent to , is adjacent to , and is adjacent to each . Then since is a smallest dominating set. If , then since is a smallest dominating set that is also independent (it is a smallest maximal independent set).
However, the bounds are simultaneously sharp for the corona of any graph , which satisfies .
Cockayne and Mynhardt characterized which sequences of values are achievable: A sequence of integers is realizable as for some graph if and only if , implies , and implies .
Determining whether for a given graph and integer 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.
A graph is called a domination-perfect graph if in every induced subgraph of . 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 for every induced subgraph with . 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.
A graph is well-covered if , 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 such that for every edge , the subgraph induced by is a complete bipartite graph. As a consequence, a tree is well-covered if and only if it is or the corona of a tree.