On the double Roman domination in graphs
| Autor: | Hossein Abdollahzadeh Ahangar, Seyed Mahmoud Sheikholeslami, Mustapha Chellali |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Vertex (graph theory)
Domination analysis Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Chordal graph Bipartite graph Discrete Mathematics and Combinatorics 0101 mathematics Arithmetic Mathematics |
| Zdroj: | Discrete Applied Mathematics. 232:1-7 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2017.06.014 |
| Popis: | A double Roman dominating function (DRDF) on a graph G = ( V , E ) is a function f : V ( G ) → { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v has at least two neighbors assigned 2 under f or one neighbor w with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v must have at least one neighbor w with f ( w ) ≥ 2 . The weight of a DRDF is the value f ( V ( G ) ) = ∑ u ∈ V ( G ) f ( u ) . The double Roman domination number γ d R ( G ) is the minimum weight of a DRDF on G . First we show that the decision problem associated with γ d R ( G ) is NP-complete for bipartite and chordal graphs. Then we present some sharp bounds on the double Roman domination number which partially answer an open question posed by Beeler et al. (2016) in their introductory paper on double Roman domination. Moreover, a characterization of graphs G with small γ d R ( G ) is provided. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect