تاريخ الرياضيات
الاعداد و نظريتها
تاريخ التحليل
تار يخ الجبر
الهندسة و التبلوجي
الرياضيات في الحضارات المختلفة
العربية
اليونانية
البابلية
الصينية
المايا
المصرية
الهندية
الرياضيات المتقطعة
المنطق
اسس الرياضيات
فلسفة الرياضيات
مواضيع عامة في المنطق
الجبر
الجبر الخطي
الجبر المجرد
الجبر البولياني
مواضيع عامة في الجبر
الضبابية
نظرية المجموعات
نظرية الزمر
نظرية الحلقات والحقول
نظرية الاعداد
نظرية الفئات
حساب المتجهات
المتتاليات-المتسلسلات
المصفوفات و نظريتها
المثلثات
الهندسة
الهندسة المستوية
الهندسة غير المستوية
مواضيع عامة في الهندسة
التفاضل و التكامل
المعادلات التفاضلية و التكاملية
معادلات تفاضلية
معادلات تكاملية
مواضيع عامة في المعادلات
التحليل
التحليل العددي
التحليل العقدي
التحليل الدالي
مواضيع عامة في التحليل
التحليل الحقيقي
التبلوجيا
نظرية الالعاب
الاحتمالات و الاحصاء
نظرية التحكم
بحوث العمليات
نظرية الكم
الشفرات
الرياضيات التطبيقية
نظريات ومبرهنات
علماء الرياضيات
500AD
500-1499
1000to1499
1500to1599
1600to1649
1650to1699
1700to1749
1750to1779
1780to1799
1800to1819
1820to1829
1830to1839
1840to1849
1850to1859
1860to1864
1865to1869
1870to1874
1875to1879
1880to1884
1885to1889
1890to1894
1895to1899
1900to1904
1905to1909
1910to1914
1915to1919
1920to1924
1925to1929
1930to1939
1940to the present
علماء الرياضيات
الرياضيات في العلوم الاخرى
بحوث و اطاريح جامعية
هل تعلم
طرائق التدريس
الرياضيات العامة
نظرية البيان
Domination Number
المؤلف:
Alikhani, S. and Peng, Y.-H
المصدر:
"Introduction to Domination Polynomial of a Graph." Ars Combin. 114
الجزء والصفحة:
...
15-3-2022
2079
+
-
20
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 | |
| antiprism graph |  |
| Apollonian network | |
| barbell graph | 2 |
book graph  |
2 |
| centipede graph |  |
cocktail party graph  |
2 |
complete graph  |
1 |
complete bipartite graph  |
2 |
complete tripartite graph  |
|
 -crossed prism graph |
 |
| crown graph | 2 |
cycle graph  |
 |
empty graph  |
 |
| gear graph | |
grid graph  |
|
| helm graph |  |
Keller graph  |
4 |
 king graph |
 |
ladder graph  |
 |
ladder rung graph  |
 |
Möbius ladder  |
![|_(n+1)/4_|+[(n+1)/4]](https://mathworld.wolfram.com/images/equations/DominationNumber/Inline86.svg) |
| 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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
الآخبار الصحية
(نوافذ).. إصدار أدبي يوثق القصص الفائزة في مسابقة الإمام العسكري (عليه السلام)
قسم الشؤون الفكرية يصدر مجموعة قصصية بعنوان (قلوب بلا مأوى)
قسم الشؤون الفكرية يصدر مجموعة قصصية بعنوان (قلوب بلا مأوى)
