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}
… excerpt ends here. Continue reading the full article.
