Magda Dettlaff
Uniwersytet Gdański

Przez graf G rozumiemy uporządkowaną parę (V, E), gdzie V jest zbiorem wierzchołków, a E zbiorem dwuelementowych podzbiorów zbioru V, czyli zbiorem krawędzi. Mówimy, że zbiór wierzchołków w grafie jest dominujący, jeśli każdy wierzchołek w grafie jest w tym zbiorze, lub jest sąsiedni (połączony krawędzią) z wierzchołkiem z tego zbioru. Oczywiście zbiór wszystkich wierzchołków w grafie G jest dominujący, dlatego nas interesuje najmniejszy zbiór dominujący w grafie, a jego moc nazywamy liczbą dominowania grafu i oznaczamy przez γ(G). W tym zakresie badane są też inne typy dominowań i liczb dominowań, gdzie zostały nałożone dodatkowe warunki na zbiór dominujący, m.in.:
ˆ -dominowanie parami (paired domination) – w podgrafie indukowanym przez zbiór dominującym jest skojarzenie doskonałe,
ˆ -dominowanie totalne (total domionation) -każdy wierzchołek w grafie ma sąsiada w zbiorze dominującym,
ˆ -dominowanie z certyfikatami (certified domination) – jeśli wierzchołek spoza zbioru dominującego ma sąsiada w zbiorze dominującym, to musi mieć co najmniej dwóch sąsiadów w tym zbiorze,
ˆ -super dominowanie (super domination) – jeśli dla każdego wierzchołka spoza zbioru dominującego, istnieje taki wierzchołek w zbiorze dominującym, dla którego jest on prywatnym sąsiadem,
ˆ- bezpieczne dominowanie włoskie (secure italian domination) – istnieje funkcja IDF, która wierzchołkom przyporządkowuje wartości 0,1 lub 2, przy czym każdy wierzchołek z wagą 0 musi mieć sąsiada z wagą 2 lub dwóch sąsiadów z wagą 1. Ponadto każdy wierzchołek v z wagą 0 ma takiego sąsiada u z wagą 1 lub 2, że f′(x) = f(x) dla x różnych od u i v oraz f′(u) = f(u) + 1, f′(v) = f(v) – 1 jest nadal funkcją IDF,
ˆ- dominowanie niezależne (independent domination) – zbiór dominujący jest niezależny.
W tym kontekście rozwazane są różne typów grafów, na przykład grafy regularne, kubiczne, zajmuje się też produktem leksykograficznym grafów oraz związkami pomiędzy poszczególnymi liczbami dominowań. Przez podział krawędzi uv w grafie G rozumiemy usunięcie tej krawędzi z grafu, dodanie do grafu nowego wierzchołka w oraz dwóch nowych krawędzi uw oraz wv. Badany jest wpływ podziału krawędzi na różne typy dominowań. W szczególności rozważany jest parametr liczby podziałowej dla tych dominowań, który jest równy najmniejszej liczbie krawędzi, które należy podzielić w grafie, aby uzyskać nowy graf z liczbą dominowania większą od liczby dominowania grafu wyjściowego. Skupimy się na klasycznym dominowaniu, dominowaniu parami oraz dominowaniu niezależnym.

Mówimy, że graf G jest doskonały (perfect) ze względu na parametry a i b, jeśli w każdym podgrafie indukowanym H grafu G zachodzi równość a(H) = b(H). Klasyczny problem grafów doskonałych dotyczy liczby chromatycznej i liczby
klikowej grafu, jednak można tę koncepcję uogólniać na inne parametry grafowe. Rozważane są grafy doskonałe ze względu na liczbę skojarzenia, liczbę dominowania słabospójnego oraz pokrycie wierzchołkowe. Ponadto rozważane są grafy doskonałe ze względu na liczbę dominowania i liczbę wspólnej niezależności grafu (największe r takie, że każdy wierzchołek należy do zbioru niezależnego mocy co najmniej r). Podane są ogólne własności takich grafów oraz charakteryzacje grafów doskonałych w języku podgrafów zabronionych. Mówimy, że graf jest doskonały (excelent) ze względu na parametr a, jeśli każdy wierzchołek grafu należy do a-zbioru (czyli zbioru o własności odpowiadającej a), np. graf jest γ-excelent jeśli każdy wierzchołek grafu należy do najmniejszego zbioru dominującego grafu (γ(G) jest liczbą dominowania grafu G). Badane są α-excelent grafy, tzn. grafy gdzie każdy wierzchołek należy do największego zbioru niezależnego. W szczególności charakteryzuje grafy blokowe, cięciwowe, dwudzielne, jednocykliczne, 2-drzewa o tej własności.

Wykład odbędzie się 18 stycznia 2024 o godzinie 17.00 przy użyciu komunikatora Zoom.