TOPICS
Search

Domination Number

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
DominatingSet

The (lower) domination number gamma(G) of a graph G is the minimum size of a dominating set of vertices in G, 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 P illustrated above, the set S={1,2,9} is a minimum dominating set, so gamma(P)=3.

The upper domination number Gamma(G) may be similarly defined as the maximum size of a minimal dominating set of vertices in G (Burger et al. 1997, Mynhardt and Roux 2020).

The (lower) irredundance number ir(G), lower domination number gamma(G), lower independence number i(G), upper independence number alpha(G), upper domination number Gamma(G), and upper irredundance number IR(G) satsify the chain of inequalities

ir(G)<=gamma(G)<=i(G)<=alpha(G)<=Gamma(G)<=IR(G)
(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).

The complete graphs K_n (each vertex is adjacent to every other), star graphs S_n (the central vertex is adjacent to all leaves), and the wheel graph W_n (the central vertex is adjacent to all rim vertices) all have domination number 1 by construction.

The domination number satisfies

n/(1+Delta)<=gamma<=n,
(2)

where n=|V| is the vertex count of a graph and Delta is its maximum vertex degree.

For a graph G with vertex count n and no isolated vertices (i.e., minimum vertex degree delta(G)>=1),

gamma(G)<=1/2n
(3)

(Ore 1962, Bujtás and Klavžar 2014). Stricter results are known when delta(G)=2, 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 gamma_t and ordinary domination number gamma satisfy

gamma<=gamma_t<=2gamma
(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 G_nOEISgamma(G_1), gamma(G_2), ...
Andrásfai graphA1587991, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, ...
Apollonian networkA0000001, 1, 3, 4, 7, 16, ...
antiprism graphA0573542, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 7, ...
barbell graphA0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
book graph S_(n+1) square P_2A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
centipede graphA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
cocktail party graph K_(n×2)A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
complete bipartite graph K_(m,n)A0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
complete graph K_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
complete tripartite graph K_(n,n,n)A0000001 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
2n-crossed prism graphA052928X, 2, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, ...
crown graphA0073952, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...
cube-connected cycle graphA0000006, 16, 46, 96, 224, 512, ...
cycle graph C_nA002264X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, ...
empty graph K^__nA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
folded cube graphA2715201, 1, 2, 4, 6, 8, 16, 32, ...
grid graph P_n square P_nA1045192, 3, 4, 7, 10, 12, 16, 20, 24, ...
grid graph P_n square P_ square P_nA2697061, 2, 6, 15, 25, 42, ...
gear graphA000000X, X, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, ...
halved cube graphA0000001, 1, 1, 2, 2, 2, 4, 7, 12, ...
helm graphA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
hypercube graph Q_nA0009831, 2, 2, 4, 7, 12, 16, 32, ...
Keller graph G_nA0000004, 4, 4, 4, ...
n×n-king graphA0755611, 1, 1, 4, 4, 4, 9, 9, 9, 16, 16, 16, 25, 25, 25, 36, ...
n×n-knight graphA0060751, 4, 4, 4, 5, 8, 10, 12, 14, 16, 21, 24, 28, 32, 36, ...
ladder graph P_2 square P_nA0045261, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ...
ladder rung graph nP_2A0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
Möbius ladder M_nA004525X, X, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 7, 7, 8, 9, 9, 9, ...
Mycielski graph M_nA0000001, 1, 2, 3, 4, 5, 6, 7, 8, ...
odd graph O_nA0000001, 1, 3, 7, 26, 66, ...
pan graphA002264X, X, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ...
path graph P_nA002264X, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, ...
prism graph Y_nA004524X, X, 2, 2, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 8, 9, 10, ...
n×n-queen graphA0754581, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, ...
Sierpiński carpet graphA0000003, 18, 130, ...
Sierpiński gasket graphA0000001, 2, 3, 9, 27, ...
star graph S_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
sun graphA004526X, X, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, ...
sunlet graph C_n circledot K_1A000000
tetrahedral Johnson graphA000000X, X, X, X, X, 2, 4, 5, 7, 8, ...
torus grid graph C_n square C_nA000000
transposition graph G_nA0000001, 1, 2, 4, 15, ...
triangular graphA0045262, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, ...
triangular honeycomb acute knight graphA0000001, 3, 3, 3, 3, 6, 9, 9, 9, 10, 15, 18, 18, 18, ...
triangular honeycomb obtuse knight graphA251534X, X, X, 4, 5, 5, 6, 6, 9, 11, 12, 14, 15, 16, 18, 19, ...
triangular honeycomb queen graphA0000001, 1, 2, 2, 3, 3, 3, 4, 4, 5, ...
triangular honeycomb rook graphA0000271, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
web graphA000027X, X, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
wheel graph W_nA0000121, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

Closed forms are summarized in the following table.

graph G_ngamma(G_n)
Andrásfai graph{1 for n=1; 2 for n=2; 3 otherwise
antiprism graph|_(2(n+2))/5_|
Apollonian network{1 for n=1,2; 1/2(3^(n-3)+5) otherwise
barbell graph2
book graph S_(n+1) square P_22
centipede graphn
cocktail party graph K_(n×2)2
complete graph K_n1
complete bipartite graph K_(m,n)2
complete tripartite graph K_(k,m,n){1 for k=1; 2 otherwise
2n-crossed prism graph2|_(n+1)/2_|
crown graph2
cycle graph C_n|_(n+2)/3_|
empty graph K^__nn
gear graph{2 for n=3; |_(n+2)/2_| otherwise
grid graph P_n square P_n{n for n<=4; 7 for n=5; 10 for n=6; 40 for n=13; |_((n+2)^2)/5_|-4 otherwise
helm graphn
Keller graph G_n4
m×n king graph|_(m+2)/3_||_(n+2)/3_|
ladder graph P_2 square P_n1+|_n/2_|
ladder rung graph nP_2n
Möbius ladder M_n|_(n+1)/4_|+[(n+1)/4]
pan graph|_(n+2)/3_|
path graph P_n|_(n+2)/3_|
prism graph Y_n|_(n+2)/4_|+|_(n+3)/4_|
m×n rook graphmin(m,n)
star graph S_n1
sun graph|_(n+1)/2_|
triangular graph|_n/2_|
triangular honeycomb rook graphn
web graphn
wheel graph W_n1

See also

Connected Domination Number, Domatic Number, Domatic Partition, Dominance, Domination Polynomial, Dominating Set, Minimum Dominating Set, Total Domination Number, Upper Domination Number, Vizing Conjecture

Portions of this entry contributed by Nicolas Bray

Explore with Wolfram|Alpha

References

Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.Bujtás, C. and Klavžar, S. "Improved Upper Bounds on the Domination Number of Graphs with Minimum Degree at Least Five." 16 Oct 2014. https://arxiv.org/abs/1410.4334.Burger, A. P.; Cockayne, E. J.; and Mynhardt, C. M. "Domination and Irredundance in the Queens' Graph." Disc. Math. 163, 47-66, 1997.Clark, W. E. and Suen, S. "An Inequality Related to Vizing's Conjecture." Electronic J. Combinatorics 7, No. 1, N4, 1-3, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Cockayne, E. J. and Mynhardt, C. M. "The Sequence of Upper and Lower Domination, Independence and Irredundance Numbers of a Graph." Disc. Math. 122, 89-102, 1993).Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 190, 1983.Goddard, W. Henning, M. A. "Domination in Planar Graphs with Small Diameter." J. Graph Th. 40, 1-25, 2002.Haynes, T. W.; Hedetniemi, S. T.; and Slater, P. J. Domination in Graphs--Advanced Topics. New York: Dekker, 1998.Haynes, T. W.; Hedetniemi, S. T.; and Slater, P. J. Fundamentals of Domination in Graphs. New York: Dekker, 1998.Henning, M. A. and Yeo, A. Total Domination in Graphs. New York: Springer, 2013.MacGillivray, G. and Seyffarth, K. "Domination Numbers of Planar Graphs." J. Graph Th. 22, 213-219, 1996.Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.Ore, O. Theory of Graphs. Providence, RI: Amer. Math. Soc., 1962.Östergård, P. R. J.; Shao, Z.; and Xu, X. "Bounds on the Domination Number of Kneser Graphs." Ars Math. Contemp. 9, 197-205, 2015.Sloane, N. J. A. Sequences A000012/M0003, A000027/M0472, A002264, A004524, A004525, A004526, A006075, A007395/M0208, A052928, A057354, A075458, A075561, A104519, A158799, A251534, A269706, and A271520 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Domination Number

Cite this as:

Bray, Nicolas and Weisstein, Eric W. "Domination Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DominationNumber.html

Subject classifications