Show simple item record

dc.contributor.authorMojdeh, Doost Ali
dc.contributor.authorSamadi, Babak
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2020-06-29T11:09:11Z
dc.date.available2020-06-29T11:09:11Z
dc.date.issued2020-05
dc.identifier.issn0399-0559
dc.identifier.issn1290-3868 (internet)
dc.identifier.urihttp://hdl.handle.net/10498/23256
dc.description.abstractIn 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.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherEDP SCIENCES S Aes_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceRAIRO-Oper. Res. 54 (2020) 1027-1040es_ES
dc.subjectGlobal defensive k-alliance number; dominating set; k-order-sum number; rooted tree; directed treees_ES
dc.subjectGlobal defensive k-alliance numberes_ES
dc.subjectdominating setes_ES
dc.subjectk-order-sum numberes_ES
dc.subjectrooted treees_ES
dc.subjectdirected treees_ES
dc.titleGlobal defensive k-alliances in directed graphs: combinatorial and computational issueses_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.identifier.doi10.1051/ro/2019049


Files in this item

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivatives 4.0 Internacional
This work is under a Creative Commons License Attribution-NonCommercial-NoDerivatives 4.0 Internacional