Search
Abstract
In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the minimum global edge alliance for certain classes: paths, cycles, wheels, complete k-partite graphs and complete k-ary trees. Moreover, we proved some lower bounds for arbitrary graphs.
Citations
-
0
CrossRef
-
0
Web of Science
-
0
Scopus
Authors (4)
Cite as
Full text
download paper
downloaded 21 times
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2018.09.002
- License
- Copyright (2018 Elsevier B.V)
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
DISCRETE APPLIED MATHEMATICS
no. 261,
pages 305 - 315,
ISSN: 0166-218X - Language:
- English
- Publication year:
- 2019
- Bibliographic description:
- Lewoń R., Małafiejska A., Małafiejski M., Wereszko K.: Global edge alliances in graphs// DISCRETE APPLIED MATHEMATICS. -Vol. 261, (2019), s.305-315
- DOI:
- Digital Object Identifier (open in new tab) 10.1016/j.dam.2018.09.002
- Verified by:
- Gdańsk University of Technology
seen 184 times