Dominating Set

For a graph  and a subset  of the vertex set , denote by  the set of vertices in  which are in  or adjacent to a vertex in . If , 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 {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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

ضمن جهوده المتواصلة.. قسم الشؤون الخدمية ينفذ حملة غسل وتنظيف لمحيط العتبة العباسية المقدسة

قسم الشؤون الفكرية يختتم مسابقة نجم الأئمة (عليهم السلام) بنسختها الخامسة في بغداد

المجمع العلمي يواصل الختمة القرآنية الرمضانية المرتلة حفظًا في مقام الإمام المهدي (عجَّل الله فرجه)

الحلقة 26 من جائزة العميد القرآنية تشهد مشاركة 5 قراء من الفتية ضمن المرحلة النهائية

المزيد

الآخبار الصحية

كوب قبل النوم.. مشروب طبيعي يحارب الأرق

دون أدوية.. طريقة طبيعية لخفض ضغط الدم بفعالية مذهلة

المعكرونة ليست عدوك.. كيف تصبح جزءا من وجبة صحية متوازنة؟

دراسة: تناول القهوة يوميا يخفض خطر الإصابة بالاضطرابات النفسية

المزيد

الآخبار التكنلوجية

علماء روس يخططون لبناء منشأة للكشف عن المادة المظلمة

ثاني أكسيد الكربون ليس تهديدا للمناخ فقط.. بل لصحة الإنسان أيضا!

ديدان الأرض تكشف تلوث التربة بالمعادن الثقيلة

خبير أرصاد جوية: ظاهرة النينيو القادمة قد تكون الأقوى خلال 10 سنوات

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength