Obiekt
Tytuł: Podziały domatyczne grafów i ich produktó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.
Abstract:
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.
Opis:
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 Ekonometriiprof. dr hab. Adam Paweł Wojda, Akademia Górniczo-Hutnicza, Wydział Matematyki Stosowanej, Katedra Matematyki Dyskretnej ; Uniwersytet Zielonogórski
Format:
Identyfikator zasobu:
Jezyk:
Prawa do dysponowania publikacją:
Biblioteka Uniwersytetu Zielonogórskiego
Kolekcje, do których przypisany jest obiekt:
- Repozytorium > Jednostki organizacyjne > Wydział Matematyki, Informatyki i Ekonometrii
- Repozytorium > Typy utworów > Rozprawy doktorskie
Data ostatniej modyfikacji:
2018-07-17
Data dodania obiektu:
2009-03-05
Liczba wyświetleń treści obiektu:
1 287
Liczba wyświetleń treści obiektu w formacie HTML
112
Wszystkie dostępne wersje tego obiektu:
https://zbc.uz.zgora.pl/repozytorium/publication/16877
Wyświetl opis w formacie RDF:
Wyświetl opis w formacie OAI-PMH:
| Nazwa wydania | Data |
|---|---|
| Kijewska, Monika, Podziały domatyczne grafów i ich produktów | 2018-07-17 |
