In graph theory, an independence dominating set for a graph G = ( V , E ) {\displaystyle G=(V,E)} is a subset D ⊆ V {\displaystyle D\subseteq V} that dominates a given independent set A {\displaystyle A} of G {\displaystyle G} ; that is, every vertex in A {\displaystyle A} is either in D {\displaystyle D} or adjacent to a vertex in D {\displaystyle D} . 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 i γ ( G ) {\displaystyle i\gamma (G)} of a graph G {\displaystyle G} is the maximum, over all independent sets A {\displaystyle A} of G {\displaystyle G} , of the smallest set dominating A {\displaystyle A} . Dominating subsets of vertices requires potentially fewer vertices than dominating all vertices, so i γ ( G ) ≤ γ ( G ) {\displaystyle i\gamma (G)\leq \gamma (G)} for all graphs G {\displaystyle G} . The inequality can be strict; there are graphs G {\displaystyle G} for which i γ ( G ) < γ ( G ) {\displaystyle i\gamma (G)<\gamma (G)} . For example, for some integer n {\displaystyle n} , let G {\displaystyle G} be a graph in which the vertices are the rows and columns of an n {\displaystyle n} -by- n {\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 i γ ( G ) = 1 {\displaystyle i\gamma (G)=1} . However, to dominate all vertices we need at least one row and one column, so γ ( G ) = 2 {\displaystyle \gamma (G)=2} . Moreover, the ratio between γ ( G ) / i γ ( G ) {\displaystyle \gamma (G)/i\gamma (G)} can be arbitrarily large. For example, if the vertices of G {\displaystyle G} are all the subsets of squares of an n {\displaystyle n} -by- n {\displaystyle n} board, then still i γ ( G ) = 1 {\displaystyle i\gamma (G)=1} , but γ ( G ) = n {\displaystyle \gamma (G)=n} .
Connection to Vizing's conjecture The independence domination number is closely connected to Vizing's conjecture, which states that for all graphs G {\displaystyle G} and H {\displaystyle H} , the domination number of the Cartesian product satisfies γ ( G ◻ H ) ≥ γ ( G ) ⋅ γ ( H ) {\displaystyle \gamma (G\mathbin {\square } H)\geq \gamma (G)\cdot \gamma (H)} . Aharoni and Szabó showed that for all graphs G {\displaystyle G} and H {\displaystyle H} ,
γ ( G ◻ H ) ≥ i γ ( G ) ⋅ γ ( H ) {\displaystyle \gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot \gamma (H)}
i γ ( G ◻ H ) ≥ i γ ( G ) ⋅ i γ ( H ) . {\displaystyle i\gamma (G\mathbin {\square } H)\geq i\gamma (G)\cdot i\gamma (H).}
Since any graph class for which γ ( G ) = i γ ( G ) {\displaystyle \gamma (G)=i\gamma (G)} automatically satisfies Vizing's conjecture, this connection motivates the study of which graph classes have this property.
… excerpt ends here. Continue reading the full article.
