Menu
A vertex of a graph \(G\) dominates itself and its neighbors. A set \(S\) of vertices of \(G\) is a dominating set if each vertex of \(G\) is dominated by some vertex of \(S\). The domination number \(\gamma(G)\) of \(G\) is the minimum cardinality of a dominating set of \(G\). A minimum dominating set is one of cardinality \(\gamma(G)\). A subset \(T\) of a minimum dominating set \(S\) is a forcing subset for \(S\) if \(S\) is the unique minimum dominating set containing \(T\). The forcing domination number \(f(S, \gamma)\) of \(S\) is the minimum cardinality among the forcing subsets of \(S\), and the forcing domination number \(f(G, \gamma)\) of \(G\) is the minimum forcing domination number among the minimum dominating sets of \(G\). For every graph \(G\), \(f(G, \gamma) \leq \gamma(G)\).
It is shown that for integers \(a, b\) with \(b\) positive and \(0 \leq a \leq b\), there exists a graph \(G\) such that \(f(G, \gamma) = a\) and \(\gamma(G) = b\). The forcing domination numbers of several classes of graphs are determined, including complete multipartite graphs, paths, cycles, ladders, and prisms. The forcing domination number of the cartesian product \(G\) of \(k\) copies of the cycle \(C_{2k+1}\) is studied. Viewing the graph \(G\) as a Cayley graph, we consider the algebraic aspects of minimum dominating sets in \(G\) and forcing subsets.