Global defensive sets in graphs - Publikacja - MOST Wiedzy


Global defensive sets in graphs


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.


  • 1
  • 0
    Web of Science
  • 1

Robert Lewoń, Anna Małafiejska, Michał Małafiejski. (2016). Global defensive sets in graphs, 339(7), 1861-1870.

Informacje szczegółowe

Publikacja w czasopiśmie
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
DISCRETE MATHEMATICS nr 339, wydanie 7, strony 1861 - 1870,
ISSN: 0012-365X
Rok wydania:
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

wyświetlono 12 razy

Publikacje, które mogą cię zainteresować

Meta Tagi