Zbiory bezpieczne w grafach

Abstract

Praca 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ą.

The thesis concerns secure sets in graphs. Let G=(V,E) be a graph with a vertex set V and an edge set E. We say that a set S that is a subset of V is secure if and only if for every subset X of S, |N[X] \cap S|>=|N[X]-S| . We consider also global secure sets, i.e., secure sets that are also dominating. It means that every vertex that does not belong to the secure set has a neighbour in it. We give upper bounds on minimum cardinalities of (global) secure sets in i.a. cubic graphs, trees, cactus trees and cographs. Moreover we investigate the question of whether a given graph contains secure sets of cardinality k, where k belongs to specified interval. In the thesis we also consider the expandability of secure sets. We say that a secure set S is expandable in G=(V,E), if |S|< |V| and there exists a vertex v that belongs to V-S such that S \cup {v} is a secure set. In the last part of the thesis we study the connection between well-known graph decomposition problems and the expansion of secure sets.