검색
Article Search

JMB Journal of Microbiolog and Biotechnology

OPEN ACCESS eISSN 0454-8124
pISSN 1225-6951
QR Code

Article

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

Published online September 30, 2021

Copyright © Kyungpook Mathematical Journal.

Complexity Issues of Perfect Roman Domination in Graphs

Padamutham Chakradhar*, Palagiri Venkata Subba Reddy

Department of Computer Science and Engineering, National Institute of Techonology, Warangal, India
e-mail : corneliusp7@gmail.com and venkatpalagiri@gmail.com

Received: November 6, 2019; Revised: October 12, 2021; Accepted: November 23, 2020

Abstract

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)=vVf(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 first 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.

Keywords: Roman domination, Perfect Roman domination, NP-complete.