2024 : 3 : 29
Doost Ali Mojdeh

Doost Ali Mojdeh

Academic rank: Professor
ORCID:
Education: PhD.
ScopusId:
Faculty: Faculty of Mathematical Sciences
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Phone: 011-35302448

Research

Title
GLOBAL DEFENSIVE k-ALLIANCES IN DIRECTED GRAPHS: COMBINATORIAL AND COMPUTATIONAL ISSUES
Type
JournalPaper
Keywords
Global defensive k-alliance number, dominating set, k-order-sum number, rooted tree, directed tree.
Year
2020
Journal RAIRO-OPERATIONS RESEARCH
DOI
Researchers Doost Ali Mojdeh ، Babak Samadi ، Ismael Gonzalez Yero

Abstract

In this paper we de ne 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 nding 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 nding a minimum global defensive (􀀀1)-alliance for any rooted tree is polynomial-time solvable.