The (lower) domination number 
of a graph 
is the minimum size of a dominating
set of vertices in 
, i.e., the size of a minimum
dominating set. This is equivalent to the smallest size of a minimal
dominating set since every minimum dominating
set is also minimal. The domination number is also equal to smallest exponent
in a domination polynomial. For example,
in the Petersen graph 
illustrated above, the set 
is a minimum
dominating set, so 
.
The upper domination number 
may be similarly defined as the maximum size of a minimal dominating set of vertices in 
(Burger et al. 1997, Mynhardt
and Roux 2020).
The (lower) irredundance number 
, lower domination number 
, lower independence
number 
,
upper independence number 
, upper domination
number 
,
and upper irredundance number 
satsify the chain of inequalities
 |
(1)
|
(Burger et al. 1997).
The domination number should not be confused with the domatic number, which is the maximum size of a domatic partition in a graph.
There are several variations of the domination number originating from variations of the underlying dominating set, the most prevalent being the total domination number (which is the minimum size of a total dominating set).
Finding a minimum dominating set, and therefore the domination number, of a general graph is NP-complete, which can be shown by reduction
from the vertex cover problem (Garey and Johnson
1983, Mertens 2024). This means that no polynomial-time algorithm exists to compute
the domination number. The fastest known algorithm to find a minimum dominating set
for a general graph with vertex count 
has time complexity 
(van Rooij and Bodlaender 2011, Mertens 2024).
The complete graphs 
(each vertex is adjacent to every other), star
graphs 
(the central vertex is adjacent to all leaves), and the wheel
graph 
(the central vertex is adjacent to all rim vertices) all have domination number 1
by construction.
The domination number satisfies
 |
(2)
|
where 
is the vertex count of a graph and 
is its maximum vertex
degree.
For a graph 
with vertex count 
and no isolated vertices (i.e., minimum
vertex degree 
),
 |
(3)
|
(Ore 1962, Bujtás and Klavžar 2014). Stricter results are known when 
,
3, etc. (cf. Bujtás and Klavžar 2014).
MacGillivray and Seyffarth (1996) showed that planar graphs with graph diameter 2 have domination number at most three and planar graphs with graph diameter 3 have domination number at most ten. Goddard and Henning (2002) showed in fact there is a unique diameter-2 planar graph with domination three (here called the Goddard-Henning graph), with all other such graphs having domination number at most 2. According to Goddard and Henning (2002), it is not known if the bound for planar diameter-3 graphs is sharp, but MacGillivray and Seyffarth (1996) gave an example of such of graph with domination number 6.
The total domination number 
and ordinary domination number 
satisfy
 |
(4)
|
(Henning and Yeo 2013, p. 17).
Östergård et al. (2015) give bounds on the domination numbers of Kneser graphs, together with a number of exact values for smaller cases.
Precomputed dominating sets for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "DominationNumber"].
The following table summarizes values of the domination number for various special classes of graphs.
graph  | OEIS |  ,  , ... |
| Andrásfai graph | A158799 | 1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ... |
| Apollonian network | A000000 | 1, 1, 3, 4, 7, 16, ... |
| antiprism graph | A057354 | 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, ... |
| barbell graph | A007395 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
book
graph  | A007395 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
| centipede graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... |
cocktail party graph  | A007395 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
complete bipartite graph  | A007395 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
complete graph  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
complete tripartite graph  | A000000 | 1 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
 -crossed
prism graph | A052928 | X, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ... |
| crown graph | A007395 | 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ... |
| cube-connected cycle graph | A000000 | 6, 16, 46, 96, 224, 512, ... |
cycle
graph  | A002264 | X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, ... |
empty graph  | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... |
| folded cube graph | A271520 | 1, 1, 2, 4, 6, 8, 16, 32, ... |
grid
graph  | A104519 | 2, 3, 4, 7, 10, 12, 16, 20, 24, ... |
grid
graph  | A269706 | 1, 2, 6, 15, 25, 42, ... |
| gear graph | A000000 | X, X, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, ... |
| halved cube graph | A000000 | 1, 1, 1, 2, 2, 2, 4, 7, 12, ... |
| helm graph | A000027 | X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... |
hypercube graph  | A000983 | 1, 2, 2, 4, 7, 12, 16, 32, ... |
Keller graph  | A000000 | 4, 4, 4, 4, ... |
 -king graph | A075561 | 1, 1, 1, 4, 4, 4, 9, 9, 9, 16, 16, 16, 25, 25, 25, 36, ... |
 -knight
graph | A006075 | 1, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, ... |
ladder graph  | A004526 | 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ... |
ladder rung graph  | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ... |
Möbius ladder  | A004525 | X, X, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8, 9, 9, 9, ... |
Mycielski graph  | A000000 | 1, 1, 2, 3, 4, 5, 6, 7, 8, ... |
odd graph  | A000000 | 1, 1, 3, 7, 26, 66, ... |
| pan graph | A002264 | X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ... |
path graph  | A002264 | X, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ... |
prism graph  | A004524 | X, X, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 10, ... |
 -queen graph | A075458 | 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, ... |
| Sierpiński carpet graph | A000000 | 3, 18, 130, ... |
| Sierpiński gasket graph | A000000 | 1, 2, 3, 9, 27, ... |
star
graph  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
| sun graph | A004526 | X, X, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, ... |
sunlet graph  | A000000 | |
| tetrahedral Johnson graph | A000000 | X, X, X, X, X, 2, 4, 5, 7, 8, ... |
torus grid graph  | A000000 | |
transposition
graph  | A000000 | 1, 1, 2, 4, 15, ... |
| triangular graph | A004526 | 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ... |
| triangular honeycomb acute knight graph | A000000 | 1, 3, 3, 3, 3, 6, 9, 9, 9, 10, 15, 18, 18, 18, ... |
| triangular honeycomb obtuse knight graph | A251534 | X, X, X, 4, 5, 5, 6, 6, 9, 11, 12, 14, 15, 16, 18, 19, ... |
| triangular honeycomb queen graph | A000000 | 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, ... |
| triangular honeycomb rook graph | A000027 | 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... |
| web graph | A000027 | X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ... |
wheel graph  | A000012 | 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... |
Closed forms are summarized in the following table.
-
![|_(n+1)/4_|+[(n+1)/4]](/images/equations/DominationNumber/Inline88.svg)
