Dorota BRÓD

(Politechnika Rzeszowska)

Charakteryzacje drzew ekstremalnych

ze względu na dominowanie

Podzbiór $S\subseteq V(G)$ nazywamy zbiorem dominującym grafu $G$, jeźeli albo wierzchołek $x$ jest w zbiorze $S$ albo jest sąsiedni z co najmniej jednym wierzchołkiem ze zbioru $S$. Podzbiór $S^* \subseteq V(G)$ nazywamy efektywnym zbiorem dominującym (z j. angielskiego efficient dominating set) grafu $G$, jeźeli $S^*$ jest zbiorem dominującym grafu $G$ i dla kaźdych dwóch róźnych $x,y \in S^*$ zachodzi $d_G(x,y)\geqslant 3$. Efektywny zbiór dominujący został wprowadzony w 1978 roku przez Bange'a, Barkauskasa i Slatera w [1].

Referat dotyczy charakteryzacji drzew ekstremalnych ze względu na liczbę zbiorów dominujących i liczbę efektywnych zbiorów dominujących. Podane zostaną podklasy drzew z największą i najmniejszą liczbą zbiorów dominujących oraz drzewa z największą liczbą efektywnych zbiorów dominujących. Problem charakteryzacji drzew z najmniejszą liczbą efektywnych zbiorów dominujących, równą zeru, został rozstrzygnięty w [2], gdzie przedstawiona została charakteryzacja strukturalna drzew, które posiadają efektywny zbiór dominujący.

W referacie wyznaczone zostaną wzory ogólne dotyczące sposobów zliczania zbiorów dominujących dowolnego grafu oraz drzewa. Przedstawione będą równieź zaleźności rekurencyjne, wraz z ich rozwiązaniami, na wyznaczanie liczby zbiorów dominujących pewnych podklas drzew. Podana zostanie charakteryzacja drzew z najmniejszą liczbą zbiorów dominujących, nazwanych minimalnymi drzewami, a takźe liczba zbiorów dominujących przedstawionych podklas drzew. Minimalne drzewa uzyskuje się z mniejszych drzew poprzez pewną konstrukcję, nawiązującą do charakteryzacji Ravindry dobrze pokrytych drzew ([5]). Podane zostaną takźe cztery, w kolejności malejącej, podklasy drzew z największymi wartościami liczb zbiorów dominujących oraz wyznaczone będą odpowiadające im liczby zbiorów dominujących.

Wyznaczona zostanie liczba efektywnych zbiorów dominujących wybranych podklas drzew oraz podane będą takźe sposoby wyznaczania liczby efektywnych zbiorów dominujących drzew spełniających pewne warunki. Ponadto przedstawione zostaną charakteryzacje drzew z największą liczbą efektywnych zbiorów dominujących. Sposób charakteryzacji tych drzew jest uzaleźniony od liczby wierzchołków drzewa.

Wyniki przedstawione w referacie pochodzą z prac [3,4] oraz stanowią treść mojej pracy doktorskiej.