A minimum dominating set is a dominating set of smallest size in a given graph. The size of a minimum dominating set is known as the domination number of the graph.
A minimum dominating set is always a minimal dominating set, but the converse does not necessarily hold.
Let 
be the family of all minimum dominating sets of a graph 
. Their intersection,
 |
is called the core of the minimum dominating sets (Bouquet et al. 2021, Chen et al. 2026). Vertices in 
were first studied for trees
by Mynhardt (1999). Following Farhan et al. (2026), such a graph
vertex is called a dominating forced vertex, and the number of such vertices
is denoted 
.
Every other graph vertex belongs either to some but
not all minimum dominating sets or to no minimum dominating set, with the latter
vertices comprising the anticore of 
(Bouquet et al. 2021).
If 
has vertex count 
and no isolated vertices,
then
 |
and the bound is sharp (Farhan et al. 2026). For example, if 
is any graph, then the graph
corona product 
, where 
is the two-vertex empty graph,
has 
as its unique minimum dominating set and therefore attains equality. The hypothesis
excluding isolated vertices is necessary since
every isolated vertex belongs to every dominating
set.
Determining whether a specified graph vertex is not a dominating forced vertex is an NP-hard decision problem (Farhan et al. 2026). For a tree, the sets of vertices belonging to every, some but not every, or no minimum dominating set can all be determined in linear time and space (Ziemann and Zyliński 2025).
The decision problem of whether a graph has a dominating set of size at most 
is NP-complete, as
can be shown by reduction from the vertex cover problem
(Garey and Johnson 1983, Mertens 2024). Consequently, a polynomial-time algorithm
for computing a minimum dominating set would imply 
. Van Rooij and Bodlaender (2011) gave an exact algorithm
that finds a minimum dominating set of a graph with vertex count 
in time 
and polynomial space.
