Zbiór dominujący

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

Liczba dominowania (Szablon:Ang.) grafu $G$ – liczba wierzchołków w najmniejszym zbiorze dominującym grafu $G.$ Liczba dominowania jest oznaczana jako $\gamma (G)$Szablon:R.

Zbiór totalnie dominujący (Szablon:Ang.) grafu $G$ – taki zbiór dominujący $V^{\prime }$ w którym każdy wierzchołek z $V^{\prime }$ ma co najmniej jednego sąsiada w $V^{\prime }.$ Oznacza to, że każdy wierzchołek z $V^{\prime }$ jest incydentalny do innego wierzchołka z $V^{\prime }$Szablon:R.

Liczba totalnego dominowania (Szablon:Ang.) grafu $G$ – liczba wierzchołków w najmniejszym zbiorze totalnie dominującym grafu $G.$ Liczba totalnego dominowania jest oznaczana jako ${\gamma }_t(G)$Szablon:R.

• 
  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