RT journal article
T1 Global defensive k-alliances in directed graphs: combinatorial and computational issues
A1 Mojdeh, Doost Ali
A1 Samadi, Babak
A1 González Yero, Ismael
A2 Matemáticas
K1 Global defensive k-alliance number; dominating set; k-order-sum number; rooted tree; directed tree
K1 Global defensive k-alliance number
K1 dominating set
K1 k-order-sum number
K1 rooted tree
K1 directed tree
AB In this paper we define the global defensive k-alliance (number) in a digraph D, and give several bounds on this parameter with characterizations of all digraphs attaining the bounds. In particular, for the case k = -1, we give a lower (an upper) bound on this parameter for directed trees (rooted trees). Moreover, the characterization of all directed trees (rooted trees) for which the equality holds is given. Finally, we show that the problem of finding the global defensive k-alliance number of a digraph is NP-hard for any suitable non-negative value of k, and in contrast with it, we also show that finding a minimum global defensive (-1)-alliance for any rooted tree is polynomial-time solvable.
PB EDP SCIENCES S A
SN 0399-0559
YR 2020
FD 2020-05
LK http://hdl.handle.net/10498/23256
UL http://hdl.handle.net/10498/23256
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 13-nov-2026