Zbiór dominujący

Zbiór dominujący (ang. Dominating set) grafu $G$ – taki podzbiór $V'$ zbioru wierzchołków $V,$ że każdy wierzchołek, który nie należy do $V'$ ma w tym zbiorze co najmniej jednego sąsiada (jest połączony krawędzią z przynajmniej jednym wierzchołkiem z $V'$).

Liczba dominowania (ang. Domination number) grafu $G$ – liczba wierzchołków w najmniejszym zbiorze dominującym grafu $G.$ Liczba dominowania jest oznaczana jako $\gamma (G)$.

Zbiór totalnie dominujący (ang. Total dominating set) grafu $G$ – taki zbiór dominujący $V'$ w którym każdy wierzchołek z $V'$ ma co najmniej jednego sąsiada w $V'.$ Oznacza to, że każdy wierzchołek z $V'$ jest incydentalny do innego wierzchołka z $V'$.

Liczba totalnego dominowania (ang. Total domination number) grafu $G$ – liczba wierzchołków w najmniejszym zbiorze totalnie dominującym grafu $G.$ Liczba totalnego dominowania jest oznaczana jako $\gamma _{t}(G)$.

• 
  Przykładowy zbiór dominujący (nie totalnie) w grafie
• 
  Przykładowy zbiór totalnie dominujący w grafie
• 
  Najmniejszy zbiór dominujący (nie totalnie), liczba dominowania – 3
• 
  Najmniejszy zbiór totalnie dominujący, liczba totalnego dominowania – 3

Zobacz też

• pokrycie wierzchołkowe
• skojarzenie
• zbiór niezależny