Dane o rozprawie doktorskiej

Rodzaj pracy	Rozprawa doktorska
Data uzyskania stopnia	04.02.2009
Uzyskany stopień naukowy	doktor nauk matematycznych
Promotor	dr hab. Maria Kwaśnik prof. PRZ Politechnika Rzeszowska, Wydział Matematyki i Fizyki Stosowanej, Katedra Matematyki
Recenzenci	prof. dr hab. Mieczysław Borowiecki, Uniwersytet Zielonogórski, Wydział Matematyki, Informatyki i Ekonometrii prof. dr hab. Adam Paweł Wojda, Akademia Górniczo-Hutnicza, Wydział Matematyki Stosowanej, Katedra Matematyki Dyskretnej
Jednostka prowadząca przewód	Uniwersytet Zielonogórski, Wydział Matematyki, Fizyki i Chemii
Miejsce pracy autora rozprawy	Akademia Morska w Szczecinie, Wydział Mechaniczny, Instytut Matematyki, Fizyki i Chemii
Dziedzina naukowa	nauki matematyczne
Dyscyplina naukowa	matematyka
Specjalność naukowa	matematyka dyskretna
Sposób zgłoszenia rozprawy, dostępność, liczba stron	ZBC, s. 109
Wydawca
Słowa kluczowe	grafy, produkty grafów, podziały domatyczne grafów, liczby domatyczne grafów

Streszczenie

Treścią pracy są podziały domatyczne grafów prostych. Podział domatyczny grafu rozumiany jako podział zbioru wierzchołków na rozłączne zbiory dominujące został wprowadzony przez E. J. Cockayne'a i S. T. Hedetniemi. Największa liczba zbiorów podziału domatycznego grafu nosi nazwę liczby domatcznej  grafu. M. R. Garey oraz D. S. Johnson wykazali, że wyznaczenie tej liczby jest problemem NP-zupełnym. Uzyskane przeze mnie wyniki można podzielić na pięć grup. Najpierw zliczone zostały podziały domatyczne grafu zwanego drogą, cyklem, grafu pełnego dwudzielnego oraz wybranych grafów domatycznie pełnych. Liczby te zostały zdefiniowane rekurencyjnie, a następnie zostały podane ich jawne postacie, m.in. przy pomocy liczb Fibonacci'ego. Do drugiej grupy wyników należą oszacowania lub dokładne wartości wybranych liczb domatycznych kilku produktów grafów, tzn. produktu kartezjańskiego dwóch grafów, produktu silnego dwóch grafów, złączenia grafów, k-korony dwóch grafów, sklejenia dwóch grafów wierzchołkami, złączenia dwóch grafów krawędzią, ściągnięcia podgrafu pełnego do nowego wierzchołka oraz duplikacji wierzchołka w grafie. Udowodnione również zostały warunki konieczne lub warunki wystarczające na to, aby dany produkt grafów był grafem domatycznie pełnym. Kolejnym rozpatrywanym zagadnieniem było ustalanie relacji pomiędzy liczbami domatycznymi grafu dwudzielnego i jego dopełnienia.  Podane zostały również pełne charakteryzacje grafów k-domatycznie krytycznych oraz grafów k-krotnie domatycznie krytycznych. Twierdzenia te są uogólnieniami klasycznych już rezultatów dotyczących grafów domatycznie krytycznych uzyskanych przez B. Zelinkę. Rozwiązane zostały również problemy typu Nordhausa-Gadduma dla liczby ps-domatycznej, k-tej liczby domatycznej oraz uzupełniającej liczby domatycznej grafu.

Abstact

Domatic partitions of graphs were investigated. The maximum number of classes of a domatic partition of a graph is called the domatic number  of a graph. The all results in the work can be divided onto five parts. The first concerns the calculating of the domatic partitions of the path, the cycle, the complete bipartite graph and some domatically full graphs. These numbers were defined recursively. Moreover, it was given the solutions of recurences using  Fibonacci numbers, generating functions. Next it was explored the bounds for the domatic numbers of graph products. It was considered the following graph products: the cartesian product of two graphs, the strong product of two graphs, the join of graphs, the k-corona of two graphs, the contraction of the complete subgraph of a graph into a new vertex and the duplication of a vertex of a graph. It was also characterized the graphs achieving the obtained bounds. Relationships between domatic numbers of the bipartite graph and its complement were established. The full characterizations of the k-domatically critical graphs and the k-tuple domatically critical graphs were also given. Several Nordhaus-Gaddum type results for domatic parameters of a graph were presented.