تسجيل الدخول

تسجيل

Domination Number

المؤلف:  Alikhani, S. and Peng, Y.-H

المصدر:  "Introduction to Domination Polynomial of a Graph." Ars Combin. 114

الجزء والصفحة:  ...

15-3-2022

3177

Domination Number

 

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 {1,2,9}" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline5.svg" style="height:22px; width:98px" /> 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).

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	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 sieve 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 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.

graph
Andrásfai graph	{1 for n=1; 2 for n=2; 3 otherwise" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline58.svg" style="height:104px; width:130px" />
antiprism graph
Apollonian network	{1 for n=1,2; 1/2(3^(n-3)+5) otherwise" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline60.svg" style="height:72px; width:277px" />
barbell graph	2
book graph	2
centipede graph
cocktail party graph	2
complete graph	1
complete bipartite graph	2
complete tripartite graph	{1 for k=1; 2 otherwise" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline67.svg" style="height:68px; width:130px" />
-crossed prism graph
crown graph	2
cycle graph
empty graph
gear graph	{2 for n=3; |_(n+2)/2_| otherwise" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline74.svg" style="height:72px; width:178px" />
grid graph	{n for n<=4; 7 for n=5; 10 for n=6; 40 for n=13; |_((n+2)^2)/5_|-4 otherwise" src="https://mathworld.wolfram.com/images/equations/DominationNumber/Inline76.svg" style="height:188px; width:251px" />
helm graph
Keller graph	4
king graph
ladder graph
ladder rung graph
Möbius ladder
pan graph
path graph
prism graph
rook graph
star graph	1
sun graph
triangular graph
triangular honeycomb rook graph
web graph
wheel graph	1

---

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."