|
چکیده
|
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
|