Global defensive k-alliances in directed graphs: combinatorial and computational issues

¹ Department of Mathematics, University of Mazandaran, Babolsar, Iran
² Departamento de Matemáticas, Universidad de Cádiz, Algeciras, Spain

^* Corresponding author: ismael.gonzalez@uca.es

Received: 4 October 2018
Accepted: 2 May 2019

Abstract

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.