Dominating Set
المؤلف:
Alikhani, S. and Peng, Y.-H.
المصدر:
Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114
الجزء والصفحة:
...
15-3-2022
1832
Dominating Set
For a graph 
and a subset 
of the vertex set 
, denote by ![N_G[S]](https://mathworld.wolfram.com/images/equations/DominatingSet/Inline4.svg)
the set of vertices in 
which are in 
or adjacent to a vertex in 
. If ![N_G[S]=V(G)](https://mathworld.wolfram.com/images/equations/DominatingSet/Inline8.svg)
, then 
is said to be a dominating set (of vertices in 
).
A dominating set of smallest size is called a minimum dominating set and its size is known as the domination number. A dominating set that is not a proper subset of any other dominating set is called a minimal dominating set.
For example, in the Petersen graph illustrated above, the set ![S=<span style=]()
{1,2,9}" src="https://mathworld.wolfram.com/images/equations/DominatingSet/Inline11.svg" style="height:22px; width:98px" /> is a dominating set (and, in fact, a minimum dominating set).
The domination polynomial encodes the numbers of dominating sets of various sizes.
Other variants of the usual dominating set can be defined, including the so-called total dominating set.
If a set is dominating and irredundant, it is maximal irredundant and minimal dominating (Mynhardt and Roux 2020).
A dominating set is minimal dominating iff it is irredundant (Mynhardt and Roux 2020).
Precomputed dominating sets for many named graphs can be obtained in the Wolfram Language using GraphData[graph, "DominatingSets"].
REFERENCES
Alikhani, S. and Peng, Y.-H. "Introduction to Domination Polynomial of a Graph." Ars Combin. 114, 257-266, 2014.
Hedetniemi, S. T. and Laskar, R. C. "A. Bibliography on Dominating Sets in Graphs and Some Basic Definitions of Domination Parameters." Disc. Math. 86, 257-277, 1990.
Mynhardt, C. M. and Roux, A. "Irredundance Graphs." 14 Apr. 2020. https://arxiv.org/abs/1812.03382.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
