Домінівна множина

У теорії графів, домінівна множина для графа ${\displaystyle G=(V,E)}$ — така підмножина ${\displaystyle D}$ множини вершин ${\displaystyle V,}$ що кожна вершина не з ${\displaystyle D}$ є суміжною зі щонайменше однією вершиною з ${\displaystyle D.}$ Число домінування ${\displaystyle \gamma (G)}$ — число вершин у найменшій домінівній множині для ${\displaystyle G.}$

Домінівні множини (червоні вершини).

Задача домінівної множини займається дослідженням чи ${\displaystyle \gamma (G)\leq K}$ для певного графа ${\displaystyle G}$ і заданого ${\displaystyle K;}$ це класична NP-повна проблема вибору в теорії складності обчислень (Garey та Johnson, 1979). Отже вважають, що не існує алгоритму з поліноміальним часом виконання, який знаходить найменшу домінівну множину для заданого графа.

Зображення (a)–(c) праворуч, наводять три приклади домінівних множин на графі. У кожному прикладі, кожна біла вершина є суміжною хоча б з однією червоною вершиною, у такому випадку кажуть, що червоні вершини домінують над білими. Число домінування цього графа є 2: Приклади (b) і (c) показують, що існують домінівні множини з 2 вершинами, і можна перевірити, що для цього графа немає домінівної множини, що складається з 1 вершини.

Межі

Нехай ${\displaystyle G}$ буде графом з ${\displaystyle n\geq 1}$ вершин і нехай ${\displaystyle \Delta }$ буде найбільшим степенем графа. Тоді відомі такі обмеження на ${\displaystyle \gamma (G)}$ (Haynes, Hedetniemi та Slater, 1998a, Chapter 2):

• Одна вершина може домінувати не більше ніж над ${\displaystyle \Delta }$ інших вершин; отже ${\displaystyle \gamma (G)\geq n/(1+\Delta ).}$
• Множина всіх вершин є домінівною множиною для будь-якого графа; отже ${\displaystyle \gamma (G)\leq n.}$
• Якщо ${\displaystyle G}$ не містить ізольованих вершин, тоді в ${\displaystyle G}$ існують дві неперетинні домінівні множини; докладніше дивись у . Отже, в будь-якому графі без ізольованих вершин ${\displaystyle \gamma (G)\leq n/2.}$

Див. також

Примітки

• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN , p. 190, problem GT2.
• Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, Marcel Dekker, ISBN , OCLC 37903553.