Article Search
eISSN 0454-8124
pISSN 1225-6951

### Article

Kyungpook Mathematical Journal 2021; 61(3): 661-669

Published online September 30, 2021

### Complexity Issues of Perfect Roman Domination in Graphs

For a simple, undirected graph G = (V, E), a perfect Roman dominating function (PRDF) f : V → {0, 1, 2} has the property that, every vertex u with f(u) = 0 is adjacent to xactly one vertex v for which f(v) = 2. The weight of a PRDF is the sum $f(V)=∑v∈Vf(v)$. The minimum weight of a PRDF is called the perfect Roman domination number, denoted by $γRP(G)$. Given a graph G and a positive integer k, the PRDF problem is to check whether G has a perfect Roman dominating function of weight at most k. In this paper, we ﬁrst investigate the complexity of PRDF problem for some subclasses of bipartite graphs namely, star convex bipartite graphs and comb convex bipartite graphs. Then we show that PRDF problem is linear time solvable for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs.