В теории графов доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в наименьшем доминирующем множестве G.
Задача о доминирующем множестве заключается в проверке, верно ли неравенство γ(G) ≤ K для заданного графа G и числа K. Задача является классической NP-полной проблемой разрешимости в теории вычислительной сложности[1]. Таким образом полагают, что не существует эффективного алгоритма для нахождения наименьшего доминирующего множества для заданного графа.
Рисунки (a)-(c) справа показывают три примера доминирующих множеств графа. В этих примерах каждая белая вершина смежна по меньшей мере одной красной вершине и говорят, что белые вершины доминируются красными вершинами. Доминирующее число этого графа равно 2 — примеры (b) и (c) показывают, что существует доминирующее множество с 2 вершинами, и можно проверить, что для данного графа не существует доминирующего множества лишь с одной вершиной.
Как заметили Хедееними и Ласкар[2], задача доминирования изучалась с 1950-х годов, но число исследований по доминированию существенно возросло в середине 1970-х. Их библиография включает более 300 статей, связанных с доминированием на графах.
Пусть G — граф с n ≥ 1 вершинами, и пусть Δ — максимальная степень графа. Известны следующие границы γ(G)[3]:
Доминирующие множества тесно связаны с независимыми множествами — независимое множество является доминирующим тогда и только тогда, когда оно является наибольшим независимым множеством, так что любое наибольшее независимое множество[4] в графе является также наименьшим доминирующим множеством. Число независимого доминирования i(G) графа G — это размер наименьшего независимого доминирующего множества (или, эквивалентно, минимальный размер наибольших независимых множеств).