Abstract | ||
---|---|---|
Abstract A signed double Roman dominating function (SDRDF) on a graph G = ( V , E ) is a function f : V ( G ) → { − 1 , 1 , 2 , 3 } such that (i) every vertex v with f ( v ) = − 1 is adjacent to at least two vertices assigned a 2 or to at least one vertex w with f ( w ) = 3 , (ii) every vertex v with f ( v ) = 1 is adjacent to at least one vertex w with f ( w ) ≥ 2 and (iii) ∑ u ∈ N [ v ] f ( u ) ≥ 1 holds for any vertex v . The weight of an SDRDF f is ∑ u ∈ V ( G ) f ( u ) , the minimum weight of an SDRDF is the signed double Roman domination number γ s d R ( G ) of G . In this paper, we prove that the signed double Roman domination problem is NP-complete for bipartite and chordal graphs. We also prove that for any tree T of order n ≥ 2 , − 5 n + 24 9 ≤ γ s d R ( T ) ≤ n and we characterize all trees attaining each bound. |
Year | Venue | DocType |
---|---|---|
2019 | Australasian J. Combinatorics | Journal |
Volume | Citations | PageRank |
72 | 0 | 0.34 |
References | Authors | |
0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
J. Amjadi | 1 | 9 | 11.54 |
Hong Yang | 2 | 0 | 1.35 |
S. Nazari-Moghaddam | 3 | 3 | 2.16 |
Seyed Mahmoud Sheikholeslami | 4 | 54 | 28.15 |
Zehui Shao | 5 | 119 | 30.98 |