Search
Abstract
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.
Citations
-
3
CrossRef
-
0
Web of Science
-
3
Scopus
Authors (3)
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.disc.2016.01.022
- License
- Copyright (2016 Elsevier B.V.)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE MATHEMATICS
no. 339,
edition 7,
pages 1861 - 1870,
ISSN: 0012-365X - Language:
- English
- Publication year:
- 2016
- Bibliographic description:
- Lewoń R., Małafiejska A., Małafiejski M.: Global defensive sets in graphs// DISCRETE MATHEMATICS. -Vol. 339, iss. 7 (2016), s.1861-1870
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.disc.2016.01.022
- Verified by:
- Gdańsk University of Technology
seen 158 times