Independence dominating set

In graph theory, an independence dominating set for a graph ${\displaystyle G=(V,E)}$ is a subset ${\displaystyle D\subseteq V}$ that dominates a given independent set ${\displaystyle A}$ of ${\displaystyle G}$; that is, every vertex in ${\displaystyle A}$ is either in ${\displaystyle D}$ or adjacent to a vertex in ${\displaystyle D}$.^[1] Unlike ordinary dominating sets, which must dominate every vertex in the graph, an independence dominating set is only required to dominate the vertices of a particular independent set.

The independence domination number ${\displaystyle i\gamma (G)}$ of a graph ${\displaystyle G}$ is the maximum, over all independent sets ${\displaystyle A}$ of ${\displaystyle G}$, of the smallest set dominating ${\displaystyle A}$.^[1] Dominating subsets of vertices requires potentially fewer vertices than dominating all vertices, so ${\displaystyle i\gamma (G)\leq \gamma (G)}$ for all graphs ${\displaystyle G}$.

The inequality can be strict; there are graphs ${\displaystyle G}$ for which ${\displaystyle i\gamma (G)<\gamma (G)}$. For example, for some integer ${\displaystyle n}$, let ${\displaystyle G}$ be a graph in which the vertices are the rows and columns of an ${\displaystyle n}$-by-${\displaystyle n}$ board, and two such vertices are connected if and only if they intersect. The only independent sets are sets of only rows or sets of only columns, and each of them can be dominated by a single vertex (a column or a row), so ${\displaystyle i\gamma (G)=1}$. However, to dominate all vertices we need at least one row and one column, so ${\displaystyle \gamma (G)=2}$. Moreover, the ratio between ${\displaystyle \gamma (G)/i\gamma (G)}$ can be arbitrarily large. For example, if the vertices of ${\displaystyle G}$ are all the subsets of squares of an ${\displaystyle n}$-by-${\displaystyle n}$ board, then still ${\displaystyle i\gamma (G)=1}$, but ${\displaystyle \gamma (G)=n}$.^[1]

The independence domination number is closely connected to Vizing's conjecture, which states that for all graphs ${\displaystyle G}$ and ${\displaystyle H}$, the domination number of the Cartesian product satisfies ${\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\cdot \gamma (H)}$.^[2] Aharoni and Szabó showed that for all graphs ${\displaystyle G}$ and ${\displaystyle H}$,^[3]

${\displaystyle \gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot \gamma (H)}$

${\displaystyle i\gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot i\gamma (H).}$

Since any graph class for which ${\displaystyle \gamma (G)=i\gamma (G)}$ automatically satisfies Vizing's conjecture, this connection motivates the study of which graph classes have this property.^[2]

For chordal graphs, the independence domination number equals the domination number: ${\displaystyle \gamma (G)=i\gamma (G)}$.^[1] This implies that Vizing's conjecture holds for chordal graphs.^[3] For strongly chordal graphs, the same equality holds since the fractional domination number equals the domination number for such graphs.^[2]

For cographs, the independence domination number has a simple characterization: ${\displaystyle i\gamma (G)}$ equals the number of connected components of ${\displaystyle G}$.^[2] This follows from the recursive structure of cographs as joins and unions: in a join ${\displaystyle G_{1}\otimes G_{2}}$, any maximal independent set is contained in one constituent and can be dominated by a single vertex from the other, giving ${\displaystyle i\gamma (G)=1}$; in a union ${\displaystyle G_{1}\oplus G_{2}}$, the independence domination numbers add.^[2]

Computing the independence domination number is NP-complete for several graph classes, including chordal graphs (since domination is already NP-complete for chordal graphs) and bipartite graphs. It is also NP-complete to decide whether ${\displaystyle i\gamma (G)\geq 2}$ for weakly chordal graphs.^[4]

On the other hand, polynomial-time algorithms exist for several restricted graph classes:^[2]

• Strongly chordal graphs
• Distance-hereditary graphs (and more generally, graphs of bounded rank-width), in ${\displaystyle O(n^{3})}$ time
• Permutation graphs, in polynomial time
• Graphs of bounded treewidth, in ${\displaystyle O(n^{3})}$ time

For general graphs, there is an exact exponential-time algorithm running in ${\displaystyle O^{*}(1.7972^{n})}$ time. This algorithm enumerates all maximal independent sets (of which there are at most ${\displaystyle 3^{n/3}}$ by the Moon–Moser bound) and finds a minimum dominating set for each using a branching strategy combined with maximum matching.^[2]

For planar graphs, there is a polynomial-time approximation scheme (PTAS) using Baker's technique of layered decomposition:^[2] for every ${\displaystyle \varepsilon >0}$, there exists a linear-time algorithm that computes a value at least ${\displaystyle (1-\varepsilon )\cdot i\gamma (G)}$. The approach partitions vertices into layers based on a plane embedding, removes periodic layers to obtain graphs of bounded treewidth, and applies the exact bounded-treewidth algorithm to each piece.

The bi-independent domination number ${\displaystyle i\gamma i(G)}$ of a graph ${\displaystyle G}$ is the maximum, over all independent sets ${\displaystyle A}$ of ${\displaystyle G}$, of the smallest independent set dominating ${\displaystyle A}$. The following relations hold for any graph ${\displaystyle G}$: $${\displaystyle {\begin{aligned}i(G)&\geq \gamma (G)\geq i\gamma (G)\\i(G)&\geq i\gamma i(G)\geq i\gamma (G)\end{aligned}}}$$ where ${\displaystyle i(G)}$ is the independent domination number.

• Independent dominating set
• Vizing's conjecture