Zbiór dominujący () grafu – taki podzbiór zbioru wierzchołków że każdy wierzchołek, który nie należy do ma w tym zbiorze co najmniej jednego sąsiada (jest połączony krawędzią z przynajmniej jednym wierzchołkiem z ).
Liczba dominowania () grafu – liczba wierzchołków w najmniejszym zbiorze dominującym grafu Liczba dominowania jest oznaczana jako .
Zbiór totalnie dominujący () grafu – taki zbiór dominujący w którym każdy wierzchołek z ma co najmniej jednego sąsiada w Oznacza to, że każdy wierzchołek z jest incydentalny do innego wierzchołka z .
Liczba totalnego dominowania () grafu – liczba wierzchołków w najmniejszym zbiorze totalnie dominującym grafu Liczba totalnego dominowania jest oznaczana jako .
Zobacz też pokrycie wierzchołkowe skojarzenie zbiór niezależny
Przypisy
Kategoria:Teoria grafów