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 |N_G(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., N_G[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 x_i for each xi∈X, c_i, a_i for each ci∈C and also create vertices a, b, c and d. Add edges a_ic_i for each c_i and c_jx_i if xi∈cj. Next, add edges x_i a for each x_i, 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(a₁) = g(a₂) = g(a₃) = 0. Since (a,cj)∈E, it follows that each vertex c_j 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 x_i's such that g(xi)≠0. Let m=|{xi:g(xi)≠0}|. The number of x_i's with g(xi)=0 is 3q-m. Since g is a PRDF, each x_i with g(xi)=0 should have exactly one neighbor c_j with g(cj)=2. So the number of c_j'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 c_i has exactly three neighbors in X, clearly, there exist q number of c_i'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 x_i for each xi∈X, c_i, a_i, ci′ for each ci∈C and also create vertices a, a^' and b. Add edges aici for each c_i 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 x_i. 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 c_i vertices with g(c_i) = 2 should be Roman dominating over all the x_j vertices in G. Then C′={ci:g(ci)=2} is an exact cover for C; because if some vertex x_i is not covered exactly once in C′, the vertex x_i 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.

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 (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 V_t, (iii) Vt1∩Vt3⊆Vt2 whenever t₁, t₂, t3∈V(T) and t₂ is on the path in T from t₁ to t₃. 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.

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.