2026-10-02T01:00:24Zhttps://repozytorium.amu.edu.pl/server/oai/request

oai:repozytorium.amu.edu.pl:10593/111912026-07-09T09:51:58Zcom_10593_51col_10593_357

Sysło, Maciej M. Promotor Jesse-Józefczyk, Katarzyna 2014-07-18T06:49:55Z 2014-07-18T06:49:55Z 2014-07-18 http://hdl.handle.net/10593/11191 Matematyki, Informatyki i Ekonometrii, Uniwersytet Zielonogórski: Zakład Matematyki Dyskretnej i Informatyki Teoretycznej 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. en koalicja alliance zbiór bezpieczny secure set zbiór dominujący dominating set Zbiory bezpieczne w grafach Secure Sets in Graphs doctoral thesis open.access