The Forcing Domination Number of a Graph

Abstract

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 )\le \gamma (G)$.It is shown that for integers $a,b$ with $b$ positive and $0\le a\le 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.