{"id":{"repo_id":"amu-pl","oai_identifier":"oai:repozytorium.amu.edu.pl:10593/11191"},"canonical_url":"https://search.dev.ndltd.org/etd/amu-pl/oai:repozytorium.amu.edu.pl:10593/11191","repository":{"repo_id":"amu-pl","name":"Poznan","base_url":"https://repozytorium.amu.edu.pl/server/oai/request"},"display":{"title":"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.","abstract_html":"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|&gt;=|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|&lt;|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|&gt;=|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|&lt; |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.","abstract_has_math":false,"creators":["Jesse-Józefczyk, Katarzyna"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-07-18","date_published":"2014-07-18","updated_at":"2026-07-27T18:44:50Z","subjects":["koalicja","alliance","zbiór bezpieczny","secure set","zbiór dominujący","dominating set"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10593/11191"],"render_values":[{"text":"hdl:10593/11191","href":null,"code":true}]}]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2014-07-18"]},{"key":"dc:type","label":"Dc Type","values":["doctoral thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["koalicja","alliance","zbiór bezpieczny","secure set","zbiór dominujący","dominating set"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["hdl:10593/11191"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.other","label":"Dc Description Other","values":["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."]},{"key":"dc:title","label":"Title","values":["Zbiory bezpieczne w grafach"]}]}],"canonical_facts":{"dc:date.issued":["2014-07-18"],"dc:description.other":["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."],"dc:identifier":["hdl:10593/11191"],"dc:subject":["koalicja","alliance","zbiór bezpieczny","secure set","zbiór dominujący","dominating set"],"dc:title":["Zbiory bezpieczne w grafach"],"dc:type":["doctoral thesis"]},"updated_at":"2026-07-27T18:44:50Z"}