Wyszukiwarka
Abstrakt
In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for each vertex v ∈ S we have SEC ({v}) = true. If S is also a dominating set of G (i.e., N [ S ] = V ( G ) ), we say that S is a global defensive alliance. We introduce the concept of defensive sets in graph G as follows: set S is a defensive set in G if and only if for each vertex v ∈ S we have SEC ({v}) = true or there exists a neighbour u of v such that u ∈ S and SEC ({v, u }) = true. Similarly, if S is also a dominating set of G, we say that S is a global defensive set. We also study the problems of total dominating alliances (total alliances) and total dominating defensive sets (total defensive sets), i.e., S is a dominating set and the induced graph G [ S ] has no isolated vertices. In the paper we proved the N P -completeness for planar bipartite subcubic graphs of the decision versions of the following minimalization problems: a global and total alliance, a global and total defensive set. We proposed polynomial time algorithms solving in trees the problem of finding the minimum total and global defensive set and the total alliance. We obtained the lower bound on the minimum size of a global defensive set in arbitrary graphs and trees.
Cytowania
-
3
CrossRef
-
0
Web of Science
-
3
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
- Wersja publikacji
- Accepted albo Published Version
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2016.01.022
- Licencja
- Copyright (2016 Elsevier B.V.)
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
DISCRETE MATHEMATICS
nr 339,
wydanie 7,
strony 1861 - 1870,
ISSN: 0012-365X - Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Lewoń R., Małafiejska A., Małafiejski M.: Global defensive sets in graphs// DISCRETE MATHEMATICS. -Vol. 339, iss. 7 (2016), s.1861-1870
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.disc.2016.01.022
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 173 razy