We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
New complexity results on Roman {2}-domination.
- Authors
Fernández, Lara; Leoni, Valeria
- Abstract
The study of a variant of Roman domination was initiated by Chellali et al. [Discrete Appl. Math.204 (2016) 22–28]. Given a graph G with vertex set V, a Roman {2}-dominating function f : V → {0, 1, 2} has the property that for every vertex v ∈ V with f(v) = 0, either there exists a vertex u adjacent to v with f(u) = 2, or at least two vertices x, y adjacent to v with f(x) = f(y) = 1. The weight of a Roman {2}-dominating function is the value f(V) = ∑v∈V f(v). The minimum weight of a Roman {2}-dominating function is called the Roman {2}-domination number and is denoted by γ{R2}(G). In this work we find several NP-complete instances of the Roman {2}-domination problem: chordal graphs, bipartite planar graphs, chordal bipartite graphs, bipartite with maximum degree 3 graphs, among others. A result by Chellali et al. [Discrete Appl. Math.204 (2016) 22–28] shows that γ{R2}(G) and the 2-rainbow domination number of G coincide when G is a tree, and thus, the linear time algorithm for k-rainbow domination due to Brešar et al. [Taiwan J. Math.12 (2008) 213–225] can be followed to compute γ{R2}(G). In this work we develop an efficient algorithm that is independent of k-rainbow domination and computes the Roman {2}-domination number on a subclass of trees called caterpillars.
- Subjects
TAIWAN; BIPARTITE graphs; DOMINATING set; PLANAR graphs; ROMANS; CATERPILLARS
- Publication
RAIRO: Operations Research (2804-7303), 2023, Vol 57, Issue 4, p1905
- ISSN
2804-7303
- Publication type
Article
- DOI
10.1051/ro/2023049