Zbiór dominujący

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

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

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

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

• 
  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

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