A function f : V(G) → {0, 1, 2} is a Roman dominating function on G if for every vertex v with f (v) = 0, there exists a vertex u ∈ N(v) such that f (u) = 2. In the literature, numerous variants of Roman domination exist, each corresponding to a specific defense strategy, and Roman {3}-domination is one such variant.
A Roman {3}-dominating function on a graph G is a function f : V (G) → {0, 1, 2, 3} having the property that for any vertex u ∈ V (G), if f (u) = 0, then ∑v∈N(u)f(v)≥3, and if f (u) = 1, then ∑v∈N(u)f(v)≥2. The weight of a Roman {3}-dominating function f is the sum f(V(G))=∑v∈V(G)f(v) and the minimum weight of a Roman {3}-dominating function on G is called the Roman {3}-domination number of G and is denoted by γ_{R3}(G).
Given a graph G, Roman {3}-domination asks to find the minimum weight of a Roman {3}-dominating function
on G. In this talk, we will explore linear-time algorithms for solving the Roman {3}-Domination problem on chain graphs and cographs.
p.s. This talk is based on the following paper https://www.sciencedirect.com/science/article/abs/pii/S0166218X22003651
