2024 : 11 : 21
Doost Ali Mojdeh

Doost Ali Mojdeh

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

Research

Title
Global offensive k-alliances in digraphs
Type
JournalPaper
Keywords
global offensive k-alliance, domination number, bipartite digraph
Year
2023
Journal Bulletin of the ICA
DOI
Researchers Doost Ali Mojdeh ، Babak Samadi ، Ismael Gonzalez Yero

Abstract

In this paper, we initiate the study of global offensive k-alliances in digraphs. Given a digraph D = (V (D), A(D)), a global offensive kalliance in a digraph D is a subset S ⊆ V (D) such that every vertex outside of S has at least one in-neighbor from S and also at least k more inneighbors from S than from outside of S, by assuming k is an integer lying between two minus the maximum in-degree of D and the maximum indegree of D. The global offensive k-alliance number γko(D) is the minimum cardinality among all global offensive k-alliances in D. In this article we begin the study of the global offensive k-alliance number of digraphs. We prove that fnding the global offensive k-alliance number of digraphs D is an NP-hard problem for any value k ∈ {2 − ∆−(D), . . . , ∆−(D)} and that it remains NP-complete even when restricted to bipartite digraphs when we consider the non-negative values of k given in the interval above. Lower bounds on γko(D) with characterizations of all digraphs attaining the bounds are given in this work. We also bound this parameter for bipartite digraphs from above. For the particular case k = 1, an immediate result from the defnition shows that γ(D) ≤ γ1o(D) for all digraphs D, in which γ(D) stands for the domination number of D. We show that these two digraph parameters are the same for some infnite families of digraphs like rooted trees and contrafunctional digraphs. Moreover, we show that the difference between γ1o(D) and γ(D) can be arbitrarily large for directed trees and connected functional digraphs