• español
    • English
  • Login
  • English 
    • español
    • English

UniversidaddeCádiz

Área de Biblioteca, Archivo y Publicaciones
Communities and Collections
View Item 
  •   RODIN Home
  • Producción Científica
  • Artículos Científicos
  • View Item
  •   RODIN Home
  • Producción Científica
  • Artículos Científicos
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Maximal double Roman domination in graphs

Identificadores

URI: http://hdl.handle.net/10498/30718

DOI: https://doi.org/10.1016/j.amc.2021.126662

ISSN: 0096-3003

Files
articulo principal (586.2Kb)
Statistics
View statistics
Metrics and citations
 
Share
Export
Export reference to MendeleyRefworksEndNoteBibTexRIS
Metadata
Show full item record
Author/s
Abdollahzadeh Ahangar, H.; Chellali, M.; Sheikholeslami, S.M.; Valenzuela Tripodoro, Juan CarlosAuthority UCA
Date
2022-02-01
Department
Matemáticas
Source
Applied Mathematics and Computation, 2022, Vol. 414
Abstract
A 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.
Subjects
Roman domination; Double Roman domination; Maximal double domination
Collections
  • Artículos Científicos [12014]
Attribution-NonCommercial-NoDerivatives 4.0 Internacional
This work is under a Creative Commons License Attribution-NonCommercial-NoDerivatives 4.0 Internacional

Browse

All of RODINCommunities and CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister

Statistics

View Usage Statistics

Información adicional

AboutDeposit in RODINPoliciesGuidelinesRightsLinksStatisticsNewsFrequently Asked Questions

RODIN is available through

OpenAIREOAIsterRecolectaHispanaEuropeanaBaseDARTOATDGoogle Academic

Related links

Sherpa/RomeoDulcineaROAROpenDOARCreative CommonsORCID

RODIN está gestionado por el Área de Biblioteca, Archivo y Publicaciones de la Universidad de Cádiz

Contact informationSuggestionsUser Support