Perfect Double Roman Domination in Graphs

By : Padamutham Chakradhar, P. Venkata Subba Reddy

Page No: 291-300

Abstract: 
For a simple, undirected, connected graph G, a Perfect Double Roman Dominating Function (PDRDF) is a function h : V(G) ? {0, 1, 2, 3} with the following two conditions.

C1). For all q Î V with h(q) = 0, either there exist exactly two vertices r1, r2 such that (q, r1) Î E, (q, r2) Î E, h(r1) = 2, h(r2) = 2 and ?s, h(s) = 3, (q, s) ? E, or there exists exactly one vertex t such that h(t) = 3, (q, t) Î E and ?u, h(u) = 2, (q, u) ? E.

C2). For all q Î V with h(q) = 1, there exists exactly one vertex r such that h(r) = 2, (q, r) Î E and ?u, h(u) = 3, (q, u) ? E.

The weight of a PDRDF g is the sum h(V) v?V h(v). = ? We show that the problem of deciding if G has a PDRDF of weight at most l for chordal and bipartite graphs is NPcomplete. Next we show that minimum weight PDRDF problem is linear time solvable for chain graphs, bounded treewidth graphs and threshold graphs. Finally, we show that PDRDF and domination problems are not equivalent in computational complexity aspects.

Authors :
Padamutham Chakradhar
Department of CSE, National Institute of Techonology, Warangal-506004, India.

P. Venkata Subba Reddy
Department of CSE, National Institute of Techonology, Warangal-506004, India.
 

DOI: https://doi.org/10.32381/JCISS.2020.45.1-4.8