Show simple item record

dc.contributor.authorAbdollahzadeh Ahangar, H.
dc.contributor.authorChellali, M.
dc.contributor.authorSheikholeslami, S.M.
dc.contributor.authorValenzuela Tripodoro, Juan Carlos 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2024-02-07T09:35:28Z
dc.date.available2024-02-07T09:35:28Z
dc.date.issued2022-02-01
dc.identifier.issn0096-3003
dc.identifier.urihttp://hdl.handle.net/10498/30718
dc.description.abstractA maximal double Roman dominating function (MDRDF) on a graph G = (V, E) is a function f:V(G)→{0,1,2,3} such that (i) every vertex v with f(v)=0 is adjacent to least two vertices assigned 2 or to at least one vertex assigned 3, (ii) every vertex v with f(v)=1 is adjacent to at least one vertex assigned 2 or 3 and (iii) the set {w∈V|f(w)=0 } is not a dominating set of G. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number is the minimum weight of an MDRDF on G. In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining the maximal double Roman domination number is NP-complete for bipartite, chordal, and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs, and distance-hereditary graphs. Moreover, we establish various relationships relating this parameter to some other domination parameters. For the class of trees, we show that for every tree T of order n≥4, 5/4 n is an upper bound for the maximal double Roman domination number and we characterize all trees attaining the bound. Finally, the exact value of this new domination parameter is given for paths and cycles.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherElsevier Inc.es_ES
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.sourceApplied Mathematics and Computation, 2022, Vol. 414es_ES
dc.subjectRoman dominationes_ES
dc.subjectDouble Roman dominationes_ES
dc.subjectMaximal double dominationes_ES
dc.titleMaximal double Roman domination in graphses_ES
dc.typejournal articlees_ES
dc.rights.accessRightsembargoed accesses_ES
dc.description.physDesc10 paginases_ES
dc.identifier.doihttps://doi.org/10.1016/j.amc.2021.126662
dc.type.hasVersionVoRes_ES


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