Abstract
dc:description.abstractPraca dotyczy zbiorów bezpiecznych w grafach. Niech G=(V,E) będzie grafem o zbiorze wierzchołków V i zbiorze krawędzi E. Mówimy, że zbiór S zawarty w V jest bezpieczny wtedy i tylko wtedy, gdy dla każdego zbioru X zawartego w S, |N[X] \cap S|>=|N[X]-S|. Rozważamy także tzw. globalne zbiory bezpieczne. Są to zbiory bezpieczne, które są jednocześnie zbiorami dominującymi, tzn. każdy wierzchołek, który nie należy do zbioru bezpiecznego, ma w nim sąsiada. W pracy podajemy ograniczenia górne na moce najmniejszych (globalnych) zbiorów bezpiecznych m.in. w grafach kubicznych, drzewach, kaktusach i kografach. Badamy także grafy pod względem zawierania zbiorów bezpiecznych o mocy k, gdzie k należy do pewnego zadanego przedziału. W pracy badamy również rozszerzalność zbiorów bezpiecznych. I tak mówimy, że zbiór bezpieczny S jest rozszerzalny w grafie G=(V,E), jeżeli |S|<|V| oraz istnieje wierzchołek v należący do V-S taki, że S \cup {v}jest zbiorem bezpiecznym. W ostatniej części pracy przedstawiamy powiązania znanych problemów dekompozycji grafów ze zbiorami bezpiecznymi oraz ich rozszerzalnością.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Jesse-Józefczyk, Katarzyna
- Advisor dc:contributor.advisor
-
- Sysło, Maciej M. Promotor
Subjects
dc:subject × 6Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Identifier
- hdl:10593/11191