In graph theory, an independent dominating set for a graph



G
=
(
V
,
E
)


{\displaystyle G=(V,E)}

is a subset



D
⊆
V


{\displaystyle 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
)


{\displaystyle i(G)}

of a graph



G


{\displaystyle G}

is the size of the smallest independent dominating set (equivalently, the smallest maximal independent set). The notation



i
(
G
)


{\displaystyle 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


{\displaystyle G}

, this minimum is the independent domination number



i
(
G
)


{\displaystyle i(G)}

. For the standard 8×8 queens graph,



α
(
G
)
=
8


{\displaystyle \alpha (G)=8}

,



i
(
G
)
=
7


{\displaystyle i(G)=7}

, and



γ
(
G
)
=
5


{\displaystyle \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


{\displaystyle n}

and maximum degree



Δ


{\displaystyle \Delta }

of a graph:

⌈


n

1
+
Δ



⌉

≤
i
(
G
)
≤
n
−
Δ


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

For graphs without isolated vertices:

i
(
G
)
≤
n
+
2
−
2


n




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

and this bound is sharp. For a graph with minimum degree at least



δ


{\displaystyle \delta }

:

i
(
G
)
≤
n
+
2
δ
−
2


δ
n




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

confirming an earlier conjecture of Favaron.

Graph families
For claw-free graphs:

i
(
G
)
=
γ
(
G
)


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

More generally, for




K

1
,
k




{\displaystyle K_{1,k}}

-free (star-free) graphs where



k
≥
3


{\displaystyle k\geq 3}

:

i
(
G
)
≤
(
k
−
2
)
γ
(
G
)
−
(
k
−
3
)


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

For any bipartite graph without isolated vertices on



n


{\displaystyle n}

vertices:

i
(
G
)
≤
n

/

2


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

For trees, if a tree has



n


{\displaystyle n}

vertices and



ℓ


{\displaystyle \ell }

leaves:

i
(
G
)
≤
(
n
+
ℓ
)

/

3


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

If



G


{\displaystyle G}

is an



r


{\displaystyle r}

-regular graph on



n


{\displaystyle n}

vertices with no isolated vertex, then:

i
(
G
)
≤
α
(
G
)
≤
n

/

2


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

For connected cubic graphs other than




K

3
,
3




{\displaystyle K_{3,3}}

:

i
(
G
)
≤
2
n

/

5


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

It has been conjectured that the bound can be improved to



3
n

/

8


{\displaystyle 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




{\displaystyle K_{3,3}}

:

i
(
G
)

/

γ
(
G
)
≤
4

/

3


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

For any planar graph on



n


{\displaystyle n}

vertices:

i
(
G
)
≤
3
n

/

4
−
2


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

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

i
(
G
)
≤
⌈
n

/

3
⌉


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

Relation to line graphs and edge domination
For any graph



G


{\displaystyle G}

, its line graph



L
(
G
)


{\displaystyle L(G)}

is claw-free, and hence a minimum maximal independent set in



L
(
G
)


{\displaystyle L(G)}

is also a minimum dominating set in



L
(
G
)


{\displaystyle L(G)}

. An independent set in



L
(
G
)


{\displaystyle L(G)}

corresponds to a matching in



G


{\displaystyle G}

, and a dominating set in



L
(
G
)


{\displaystyle L(G)}

corresponds to an edge dominating set in



G


{\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),



γ
(
G
)
≤
i
(
G
)


{\displaystyle \gamma (G)\leq i(G)}

for all graphs



G


{\displaystyle G}

. Similarly, since every maximal independent set is an independent set,



i
(
G
)
≤
α
(
G
)


{\displaystyle i(G)\leq \alpha (G)}

, where



α
(
G
)


{\displaystyle \alpha (G)}

is the independence number. Furthermore, since every maximal independent set is a minimal dominating set,



α
(
G
)
≤
Γ
(
G
)


{\displaystyle \alpha (G)\leq \Gamma (G)}

, where



Γ
(
G
)


{\displaystyle \Gamma (G)}

is the upper domination number (the maximum size of a minimal dominating set). This yields the domination chain:

γ
(
G
)
≤
i
(
G
)
≤
α
(
G
)
≤
Γ
(
G
)
.


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

The inequality can be strict; there are graphs



G


{\displaystyle G}

for which



γ
(
G
)
<
i
(
G
)


{\displaystyle \gamma (G)<i(G)}

. For example, let



G


{\displaystyle G}

be the double star graph consisting of vertices




x

1


,
…
,

x

p


,
a
,
b
,

y

1


,
…
,

y

q




{\displaystyle x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}}

, where



p
,
q
>
1


{\displaystyle p,q>1}

. The edges of



G


{\displaystyle G}

are defined as follows: each




x

i




{\displaystyle x_{i}}

is adjacent to



a


{\displaystyle a}

,



a


{\displaystyle a}

is adjacent to



b


{\displaystyle b}

, and



b


{\displaystyle b}

is adjacent to each




y

j




{\displaystyle y_{j}}

. Then



γ
(
G
)
=
2


{\displaystyle \gamma (G)=2}

since



{
a
,
b
}


{\displaystyle \{a,b\}}

is a smallest dominating set. If



p
≤
q


{\displaystyle p\leq q}

, then



i
(
G
)
=
p
+
1


{\displaystyle i(G)=p+1}

since



{

x

1


,
…
,

x

p


,
b
}


{\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



γ
(
G
)
≤
i
(
G
)
≤
α
(
G
)


{\displaystyle \gamma (G)\leq i(G)\leq \alpha (G)}

are simultaneously sharp for the corona



H
∘

K

1




{\displaystyle H\circ K_{1}}

of any graph



H


{\displaystyle H}

, which satisfies



γ
(
G
)
=
i
(
G
)
=
α
(
G
)
=

|

V
(
H
)

|



{\displaystyle \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


)


{\displaystyle (s_{1},s_{2},s_{3},s_{4})}

of integers is realizable as



(
γ
(
G
)
,
i
(
G
)
,
α
(
G
)
,
Γ
(
G
)
)


{\displaystyle (\gamma (G),i(G),\alpha (G),\Gamma (G))}

for some graph



G


{\displaystyle G}

if and only if



1
≤

s

1


≤

s

2


≤

s

3


≤

s

4




{\displaystyle 1\leq s_{1}\leq s_{2}\leq s_{3}\leq s_{4}}

,




s

1


=
1


{\displaystyle s_{1}=1}

implies




s

2


=
1


{\displaystyle s_{2}=1}

, and




s

3


=
1


{\displaystyle s_{3}=1}

implies




s

4


=
1


{\displaystyle s_{4}=1}

.

Computational complexity
Determining whether



i
(
G
)
≤
k


{\displaystyle i(G)\leq k}

for a given graph



G


{\displaystyle G}

and integer



k


{\displaystyle 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


{\displaystyle G}

is called a domination-perfect graph if



γ
(
H
)
=
i
(
H
)


{\displaystyle \gamma (H)=i(H)}

in every induced subgraph



H


{\displaystyle H}

of



G


{\displaystyle 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



γ
(
H
)
=
i
(
H
)


{\displaystyle \gamma (H)=i(H)}

for every induced subgraph



H


{\displaystyle H}

with



γ
(
H
)
=
2


{\displaystyle \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
)
=
α
(
G
)


{\displaystyle 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


{\displaystyle M}

such that for every edge



u
v
∈
M


{\displaystyle uv\in M}

, the subgraph induced by



N
[
u
]
∪
N
[
v
]


{\displaystyle 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




{\displaystyle K_{1}}

or the corona of a tree.

See also
Independence dominating set
Dominating set
Maximal independent set
Well-covered graph

References