Article Search
eISSN 0454-8124
pISSN 1225-6951

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

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.

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

Let G = (V, E) be a simple, undirected and connected graph with no isolated vertices. For a vertex v ∈ V, the open neighborhood of v in G is $NG(v)={u∣u∈V,(u,v)∈E}$ and the closed neighborhood of v is defined as $NG[v]=NG(v)∪{v}$. The degree deg(v) of a vertex v is |NG(v)|. The maximum degree of a graph G, denoted by Δ and minimum degree of a graph, denoted by δ are the maximum and minimum degree of its vertices. An induced subgraph is a graph formed from a subset D of vertices of G and all of the edges in G connecting pairs of vertices in that subset, denoted by $⟨D⟩$. A clique is a subset of vertices of G such that every two distinct vertices in the subset are adjacent. An independent set is a set of vertices in which no two vertices are adjacent. A vertex v of G is said to be a pendant vertex if deg(v) = 1. A vertex v is called isolated vertex if deg(v) = 0. A bipartite graph G = (X, Y, E) is called tree convex if there exists a tree T = (X, F) such that, for each y in Y, the neighbors of y induce a subtree in T. When T is a star (comb), G is called star (comb) convex bipartite graph [6]. For undefined terminology and notations we refer the reader to [3].

A vertex v in G dominates the vertices of its closed neighborhood. A set of vertices $S⊆V$ is a dominating set (DS) in G if for every vertex $u∈V∖S$, there exists at least one vertex v ∈ S such that $(u,v)∈E$, i.e., NG[S] = V. A vertex $u∈V∖S$ is said to be undominated if $NG(u)∩S=∅$. The domination number is the minimum cardinality of a dominating set in G and is denoted by γ(G) [15].

Roman domination has been introduced by Cockayne et al. in [4]. A function $f:V→{0,1,2}$ is a Roman Dominating Function (RDF) on G if every vertex u ∈ V for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. In this case, we say that u is Roman dominated by v or v Roman dominates u. The weight of an RDF is the value $f(V)=∑ u∈Vf(u)$. The Roman domination number is the minimum weight of an RDF on G and is denoted by γR(G). The literature on Roman domination in graphs has been surveyed in [10, 12].

The concept of perfect Roman domination was introduced in 2018 by Henning et al. in [8]. A function $f:V→{0,1,2}$ is a perfect Roman Dominating Function (PRDF) on G, if every vertex u ∈ V for which f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The weight of a PRDF is the value $f(V)=∑ u∈Vf(u)$. The perfect Roman domination number is the minimum weight of a PRDF on G and is denoted by $γRP(G)$. The perfect Roman domination has been studied in [14, 9].

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. Banerjee et al. in [14] proved that the PRDF problem is NP-complete for planar graphs, bipartite graphs and chordal graphs. In this paper we strengthen the result for bipartite graph by showing that this problem remains NP-complete for two subclasses of bipartite graphs, i.e., star convex and comb convex bipartite graphs.

In this section, we show that the PRDF problem is NP-complete for star convex bipartite graphs and comb convex bipartite graphs by giving a polynomial time reduction from a well-known NP-complete problem, Exact-3-Cover (X3C)[7], which is defined as follows.

EXACT-3-COVER (X3C)

INSTANCE : A finite set X with $∣X∣=3q$ and a collection C of three-element subsets of X.

QUESTION : Is there a subcollection $C′$ of C such that every element of X appears in exactly one member of $C′$?

The decision version of perfect Roman dominating function problem is defined as follows.

PERFECT ROMAN DOMINATING FUNCTION PROBLEM (PRDFP)

INSTANCE : A simple, undirected graph G = (V, E) and a positive integer $k≤∣V∣$.

QUESTION : Does G have a perfect Roman dominating function of weight at most k?

Theorem 2.1. PRDFP is NP-complete for star convex bipartite graphs.

Proof. Given any function $f:V→{0,1,2}$ and a positive integer $k≤|V|$, we can check in polynomial time whether $f(V)≤k$ and for every vertex u ∈ V with f(u) = 0, there is exactly one vertex $v∈NG(u)$ such that f(v) = 2. So the PRDFP is a member of NP. We transform an instance of X3C, where $X={x1,x2,...,x3q}$ and $C={c1,c2,...,ct}$, to an instance of PRDFP as follows.

Create vertices xi for each $xi∈X$, ci, ai for each $ci∈C$ and also create vertices a, b, c and d. Add edges aici for each ci and cjxi if $xi∈cj$. Next, add edges xi a for each xi, ba, bc and bd. Let $A={ci:1≤i≤t}∪{a,c,d}$, $B={xi:1≤i≤3q}$ ${ai:1≤i≤t}∪{b}$. The set A induces a star with vertex a as central vertex as shown in the Figure 1. From the Figure 2, it is clear that the graph constructed is a star convex bipartite graph since the neighbors of each element in B induce a subtree of star, where $|V|=2t+3q+4$ and $|E|=3q+4t+3$. Next, we show that X3C has a solution if and only if G has a PRDF with weight at most 2t+2. Let k = 2t+2.

Figure 1. Star Graph
Figure 2. Construction of a star convex bipartite graph from an instance of X3C

Suppose $C′$ is a solution for X3C with $|C′| =q$. We construct a perfect Roman dominating function f on G as follows.

Clearly, $f(V)≤2q+2=k$.

Conversely, suppose that G has a perfect Roman dominating function g with weight at most k. Clearly, $g(a)+g(a1)+g(a2)+g(a3)≥2$. Without loss of generality, let g(a) = 2 and g(a1) = g(a2) = g(a3) = 0. Since $(a,cj)∈E$, it follows that each vertex cj may be assigned the value 0.

Claim 1.1. If g(V) = k then for each $xi∈X$, $g(xi)=0$.

Proof. (Proof by contradiction) Assume g(V) = k and there exist some xi's such that $g(xi)≠0$. Let $m=|{xi:g(xi)≠0}|$. The number of xi's with $g(xi)=0$ is 3q-m. Since g is a PRDF, each xi with $g(xi)=0$ should have exactly one neighbor cj with $g(cj)=2$. So the number of cj's required with $g(cj)=2$ is $3q−m3$. Hence $g(V)=2+m+23q−m3=2+2q+m3$, which is greater than k, a contradiction. Therefore for each $xi∈X$, $g(xi)=0$.

Since each ci has exactly three neighbors in X, clearly, there exist q number of ci's with weight 2 such that $(∪ g(ci)=2NG(ci))∩X=X$. Consequently, $C′={ci:g(ci)=2}$is an exact cover for C.

Theorem 2.2. PRDFP is NP-complete for comb convex bipartite graphs. Proof. Clearly, PRDFP is a member of NP. We transform an instance of X3C, where $X={x1,x2,...,x3q}$ and $C={c1,c2,...,ct}$, to an instance of PRDFP as follows.

Create vertices xi for each $xi∈X$, ci, ai, $ci′$ for each $ci∈C$ and also create vertices a, a' and b. Add edges $aici$ for each ci and $cjxi$ if $xi∈cj$. Next add edges $cj′b$ for each $cj′$, ba and $ba′$. Also add edges by joining each $cj′$ to every xi. Let $A={a,a′}∪{ci,ci′:1≤i≤t}$ and $B=V∖A$. The set A induces a comb with elements ${ci′:1≤i≤t}∪{a′}$ as backbone and ${ci:1≤i≤t}∪{a}$ as teeth as shown in the Figure 3. From the Figure 4, it is clear that the graph constructed is a comb convex bipartite graph since the neighbors of each element in B induce a subtree of the comb, where |V| = 3t+3q+3 and |E| = 3qt+5t+2. Next we show that, X3C has a solution if and only if G has a PRDF with weight at most 2t+2.

Figure 3. Comb Graph
Figure 4. Construction of a comb convex bipartite graph from an instance of X3C

Suppose $C′$ is a solution for X3C with $|C′| =q$. We construct a perfect Roman dominating function f on G as follows.

Clearly, $f(V)≤2t+2$.

Conversely, suppose that G has a perfect Roman dominating function g with weight at most 2t+2. Clearly, for each i, $g(ai)+g(ci)≥2$, these make the size at least 2t, and $g(b)+g(a)+g(a′)≥2$. Without loss of generality, g(b) = 2, g(a) = 0, $g(a′)=0$, $g(xi)=0$ where $1≤i≤3q$ and $g(cj′)=0$ where $1≤j≤t$. Since g is a perfect Roman dominating function with weight 2t+2 or less, the ci vertices with g(ci) = 2 should be Roman dominating over all the xj vertices in G. Then $C′={ci:g(ci)=2}$ is an exact cover for C; because if some vertex xi is not covered exactly once in $C′$, the vertex xi would not be Roman dominated exactly once in G and g would not be a PRDF.

Now, the following result is immediate from Theorem 2.1 and Theorem 2.2.

Theorem 2.3. PRDFP is NP-complete for tree convex bipartite graphs.

In this section, we determine the perfect Roman domination number of threshold graph.

Definition 3.1. A graph G = (V, E) is called a threshold graph if there is a real number T and a real number w(v) for every v ∈ V such that a set $S⊆V$ is independent if and only if $∑ v∈Sw(S)≤T$.

Although several characterizations defined for threshold graphs, We use the following characterization of threshold graphs given in [11] to prove that the perfect Roman domination number can be computed in linear time for threshold graphs.

A graph G = (V, E) is a threshold graph if and only if it is a split graph and, for split partition (C, I) of V where C is a clique and I is an independent set, there is an ordering ${x1,x2,…,xp}$ of vertices of C such that $NG[x1]⊆NG[x2]⊆NG[x3]⊆…⊆NG[xp]$, and there is an ordering ${y1,y2,…,yq}$ of the vertices of I such that $NG(y1)⊇NG(y2)⊇NG(y3)⊇…⊇NG(yq)$. If |C|=0 then, weight 1 is assigned for each vertex, clearly, $γRP(G)=|V|$. If $|C|>0$ then the following theorem holds.

Theorem 3.2. Let G be a threshold graph. Then $γRP(G)=k+1$, where k is the number of connected components in G.

Proof. Let G be a threshold graph with p clique vertices such that $NG[x1]⊆NG[x2]⊆NG[x3]⊆…⊆NG[xp]$. Now, define a function $f:V→{0,1,2}$ as follows.

$f(v)=1,if deg(v)=02,if v=xp0,otherwise$

Clearly, f is a PRDF and $γRP(G)≤k+1$. From the definition of PRDF, it follows that $γRP(G)≥k+1$. Therefore $γRP(G)=k+1$.

Now, the following result is immediate from Theorem 3.1.

Theorem 3.3. PRDF problem can be solvable in linear time for threshold graphs.

Proof. Since the ordering of the vertices of the clique and the number of connected components in a threshold graph can be determined in linear time [2, 11], the result follows.

In this section, we propose a method to compute the perfect Roman domination number of a chain graph in linear time. A bipartite graph G = (X, Y, E) is called a chain graph if the neighborhoods of the vertices of X form a chain, that is, the vertices of X can be linearly ordered, say $x1,x2,...,xp$, such that $NG(x1)⊆NG(x2)⊆...⊆NG(xp)$. If G = (X, Y, E) is a chain graph, then the neighborhoods of the vertices of Y also form a chain. An ordering $α=(x1,x2,…,xp,y1,y2,…,yq)$ of $X∪Y$ is called a chain ordering if $NG(x1)⊆NG(x2)⊆...⊆NG(xp)$ and $NG(y1)⊇NG(y2)⊇...⊇NG(yq)$. Every chain graph admits a chain ordering [5].The following proposition is stated in [4].

Proposition 4.1. Let $G=Km1,…,mn$ be the complete n-bipartite graph with $m1≤m2≤...≤mn$.

(a) If $m1≥3$ then $γR(G)=4$.

(b) If $m1=2$ then $γR(G)=3$.

(c) If $m1=1$ then $γR(G)=2$.

If G(X, Y, E) is a complete bipartite graph then, clearly, $γR(G)=γRP(G)$ i.e., $γRP(G)$ is obtained directly from Proposition 4.1. Otherwise, the following theorem holds.

Theorem 4.2. Let $G(X,Y,E)(≇Kr,s)$ be a chain graph. Then,

Proof. If $G≅K1$ then $γRP(G)=1$. Otherwise, let G(X, Y, E) be a chain graph with |X| = p and |Y| = q. Now, define a function $f:V→{0,1,2}$

$Case(1):|X|=2 and |Y|=2 then f(v)=2,if v=y11,if v=y20,otherwise$ $Case(2):|X|=2 and |Y|≠2 then f(v)=2,if v=x21,if v=x10,otherwise$

Case (3) : $|X|≠2$ and |Y| = 2 then same condition holds as in Case (1).

Clearly, f is a PRDF and $γRP(G)≤3$. From the definition of PRDF, it follows that $γRP(G)≥3$. Therefore $γRP(G)=3$.

Case (4) : $|X|≠2$ and $|Y|≠2$ then $f(v)=2,if v∈{xp,y1}0,otherwise$

Clearly, f is a PRDF and $γRP(G)≤4$.

Since p ≥ 2 and q ≥ 2, in any PRDF of G, $f(X)≥2$ and $f(Y)≥2$. Therefore $γRP(G)≥4$. Hence $γRP(G)=4$.

If the chain graph G is disconnected with k connected components $G1,G2,…,Gk$ then it is easy to verify that $γRP(G)=∑ i=1kγRP(Gi)$.

Theorem 4.3. PRDF problem can be solvable in linear time for chain graphs.

Proof. Since the chain ordering and the connected components can be computed in linear time [2, 13], the result follows.

Let G be a graph, T be a tree and v be a family of vertex sets $Vt⊆V(G)$ indexed by the vertices t of T . The pair (T, v ) is called a tree-decomposition of G if it satisfies the following three conditions: (i) $V(G)=∪ t∈V(T)Vt$, (ii) for every edge $e∈E(G)$ there exists a $t∈V(T)$ such that both ends of e lie in Vt, (iii) $Vt1∩Vt3⊆Vt2$ whenever t1, t2, $t3∈V(T)$ and t2 is on the path in T from t1 to t3. The width of (T, v ) is the number $max{|Vt|−1:t∈T}$, and the tree-width tw(G) of G is the minimum width of any tree-decomposition of G. By Courcelle's Thoerem, it is well known that every graph problem that can be described by counting monadic second-order logic (CMSOL) can be solved in linear-time in graphs of bounded tree-width, given a tree decomposition as input [1]. We show that PRDF problem can be expressed in CMSOL.

Theorem 5.1.([Courcelle's Theorem][1]) Let P be a graph property expressible in CMSOL and k be a constant. Then, for any graph G of tree-width at most k, it can be checked in linear-time whether G has property P.

Theorem 5.2. Given a graph G and a positive integer k, PRDF can be expressed in CMSOL.

Proof. Let $f=(V0,V1,V2)$ be a function $f:V→{0,1,2}$ on a graph G, where $Vi={v|f(v)=i}$ for $i∈{0,1,2}$. The CMSOL formula for the PRDF problem is expressed as follows.

$Perfect_Rom_Dom(V)=(f(V)≤k)∧∃V0,V1,V2,∀p((p∈V1)∨(p∈V2)∨(p∈V0∧∃r(r∈V2∧adj(p,r))∧¬(∃s,s∈V2∧s≠r∧adj(p,s))),$

where adj(p, q) is the binary adjacency relation which holds if and only if, p, q are two adjacent vertices of G.

Now, the following result is immediate from Theorem 5.1 and Theorem 5.2.

Theorem 5.3. PRDF problem can be solvable in linear time for bounded tree-width graphs.

In this paper, we have shown that the decision problem associated with $γRP(G)$ is NP-complete for some subclasses of bipartite graphs. Next, we have shown that PRDF problem is linear time solvable for bounded tree-width graphs, threshold graphs and chain graphs. Investigating the algorithmic complexity of this problem for other subclasses of bipartite graphs and chordal graphs remains open.

1. B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inf. Comput., 85(1990), 12-75.
2. C. E. Leiserson, R. L. Rivest, T. H. Cormen and C. Stein, Introduction to algorithms, MIT press Cambridge, MA, 2001.
3. D. B. West, Introduction to Graph Theory, Upper Saddle River: Prentice hall, 2001.
4. E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi and S. T. Hedetniemi, Roman domination in graphs, Discrete Math., 278(2004), 11-22.
5. M. Yannakakis, Node-and edge-deletion np-complete problems, In Proceedings of the Tenth Annual ACM Symposium on Theo. of Comp. STOC, New York, USA, (1978), 253-264.
6. M. Lin and C. Chen, Counting independent sets in tree convex bipartite graphs, Discrete Appl. Math., 218(2017), 113-122.
7. M. R. Garey and D. S. Johnson, Computers and Interactability : A Guide to the Theory of NP-completeness, Freeman, New York, 1979.
8. M. A. Henning, W. F. Klostermeyer and G. MacGillivray, Perfect Roman domination in trees, Discrete Appl. Math., 236(2018), 235-245.
9. M. Darkooti, A. Alhevaz, S. Rahimi and H. Rahbani, On perfect Roman domination number in trees: complexity and bounds, Journal of Combinatorial Optimization, 38(2019), 712-720.
10. N. J. Rad and L. Volkmann, Roman domination perfect graphs, An. Stiint. Univ. Ovidius Constanta Ser. Mat., 19(2019), 167-174.
11. N. Mahadev and U. Peled, Threshold graphs and related topics, in: Annals of Discrete Mathematics, North Holland, 1995.
12. O. Favaron H. Karami, R. Khoeilar and S. M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math., 309(2009), 3447-3451.
13. R. Uehara and Y. Uno, Efficient algorithms for the longest path problem, International symposium on algorithms and computation, (2004), 871-883.
14. S. Banerjee, J. Mark Keil and D. Pradhan, Perfect Roman domination in graphs, Theor. Comput. Sci., (2019) (Submitted).
15. T. W. Haynes, S. Hedetniemi and P. Slater, Fundamentals of domination in graphs, CRC Press, 1998.