Object
Title: Podziały domatyczne grafów i ich produktów
Abstract_pl:
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.
Description:
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:
Resource Identifier:
Language:
Rights:
Biblioteka Uniwersytetu Zielonogórskiego
Object collections:
- Digital Library of Zielona Góra > Repository > Faculties > Faculty of Mathematics, Computer Science and Econometrics
- Digital Library of Zielona Góra > Repository > Types of work > Dissertations
Last modified:
Jul 17, 2018
In our library since:
Mar 5, 2009
Number of object content hits:
1 287
Number of object content views in HTML format
112
All available object's versions:
https://zbc.uz.zgora.pl/publication/16877
Show description in RDF format:
Show description in OAI-PMH format:
| Edition name | Date |
|---|---|
| Kijewska, Monika, Podziały domatyczne grafów i ich produktów | Jul 17, 2018 |
