Nader Jafari Rad^a , Elahe Shabani^b

n.jafarirad@gmail.com, e−shabani6480@yahoo.com

A hop Roman dominating function (HRDF) on a graph G = (V, E) is a function f : V −→ {0, 1, 2} having the property that for every vertex v ∈ V with f(v) = 0 there is a vertex u with f(u) = 2 and d(u, v) = 2. The weight of an HRDF f is the sum of its values on V . The minimum weight of an HRDF on G is called the hop Roman domination number of G. An HRDF f is a hop Roman independent dominating function (HRIDF) if for any pair v, w with f(v) > 0 and f(w) > 0, d(v, w) 6= 2. The minimum weight of an HRIDF on G is called the hop Roman independent domination number of G. In this paper, we study the complexity of the hop independent dominating problem, the hop Roman domination function problem and the hop Roman independent domination function problem, and show that the decision problem for each of the above three problems is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Keywords: dominating set, hop dominating set, hop independent set, hop Roman dominating function, hop Roman independent dominating function, complexity

Mathematics Subject Classification : 05C69

DOI: 10.5614/ejgta.2019.7.1.6

1. Introduction

For notation and graph theory terminology not given here, we refer to [6]. Let G = (V, E) be a graph with vertex set V = V (G) and edge set E = E(G). The order of G is n(G) = |V (G)|. The open neighborhood of a vertex v is NG(v) = {u ∈ V (G)| uv ∈ E(G)}. The degree of v, denoted

Received: 2 March 2018, Revised: 24 December 2018, Accepted: 5 January 2019.

^aDepartment of Mathematics, Shahed University, Tehran, Iran.

^bFaculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran.

by \(\deg(v)\), is \(|N_G(v)|\). A vertex of degree one in a tree is referred as a leaf and its unique neighbor as a \(support\ vertex\). The \(open\ neighborhood\) of a subset \(S\subseteq V\), is \(N_G(S)=\bigcup_{v\in S}N_G(v)\), and the \(closed\ neighborhood\) of S is the set \(N_G[S]=N_G(S)\cup S\). The distance between two vertices u and v in G, denoted by d(u,v), is the minimum length of a (u,v)-path in G. A \(bipartite\ graph\) is a graph whose vertices can \(chordal\ graph\) is a graph that does not contain an induced cycle of length greater than S. A S S S S S S S S S S

Ayyaswamy and Natarajan [2] introduced the concept of hop domination in graphs. A subset S of vertices of a graph G is a hop dominating set (HDS) if every vertex outside S is at distance two from a vertex of S. The hop domination number, \(\gamma_h(G)\), of G is the minimum cardinality of an HDS of G. An HDS of G of minimum cardinality is referred to a \(\gamma_h(G)\)-set. The concept of hop domination was further studied, for example, in [1, 4, 7, 9]. For a subset \(S \subseteq V(G)\) and a vertex \(v \in V(G)\), we say that v is hop dominated by S (or S hop dominates v) if either \(v \in S\) or \(v \notin S\) and d(u,v)=2 for some vertex \(u \in S\). Ayyaswamy and Natarajan [9] also introduced the concept of hop independent domination in graphs. A subset S of vertices of a graph G is a hop independent domination set (HIDS) if S is a HDS and for any pair \(v, w \in S\), \(d(v, w) \neq 2\). The hop independent domination number, \(\gamma_{hi}(G)\), of G is the minimum cardinality of an HIDS of G.

A function \(f:V\longrightarrow\{0,1,2\}\) having the property that for every vertex \(v\in V\) with f(v)=0, there exists a vertex \(u\in N(v)\) with f(u)=2, is called a Roman dominating function or just an RDF. The weight of an RDF f is the sum \(f(V)=\sum_{v\in V}f(v)\). The minimum weight of an RDF on G is called the Roman domination number of G and is denoted by \(\gamma_R(G)\). For an RDF f in a graph G, we denote by \(V_i\) (or \(V_i^f\) to refer to f) the set of all vertices of G with label i under f. Thus an RDF f can be represented by a triple \((V_0,V_1,V_2)\), and we can use the notation \(f=(V_0,V_1,V_2)\). The mathematical concept of Roman domination, was defined and discussed by Stewart [12], and ReVelle and Rosing [10], and was subsequently developed by Cockayne et al. [3].

Shabani [11] introduced the concept of hop Roman dominating functions. A hop Roman dominating function (HRDF) is a function \(f:V\longrightarrow\{0,1,2\}\) having the property that for every vertex \(v\in V\) with f(v)=0 there is a vertex u with f(u)=2 and d(u,v)=2. The weight of an HRDF f is the sum \(f(V)=\sum_{v\in V}f(v)\). The minimum weight of an HRDF on G is called the hop Roman domination number of G and is denoted \(\gamma_{hR}(G)\). An HRDF with minimum weight is referred as a \(\gamma_{hR}(G)\)-function. For an HRDF f in a graph G, we denote by \(V_i\) (or \(V_i^f\) to refer to f) the set of all vertices of G with label i under f. Thus an HRDF f can be represented by a triple \((V_0,V_1,V_2)\), and we can use the notation \(f=(V_0,V_1,V_2)\). For a function \(f=(V_0,V_1,V_2)\) and a vertex \(v\in V(G)\), we say that v is hop Roman dominated by f (or f hop Roman dominates v), if either \(v\in V_1\cup V_2\) or there exist \(u\in V_2\), such that d(v,u)=2. An HRDF \(f=(V_0,V_1,V_2)\) is a hop Roman independent dominating function(HRIDF) if for any pair \(v,w\in V_1\cup V_2\), \(d(v,w)\neq 2\). The minimum weight of an HRIDF on G is called the hop Roman independent domination number of G and is denote \(\gamma_{hRI}(G)\).

In this paper we study the complexity of the hop independent dominating problem, the hop Roman domination function problem and the hop Roman independent domination function problem, and show that the decision problem for each of the above three problems is NP-complete even

when restricted to planar bipartite graphs or planar chordal graphs. We use a transformation of the Vertex Cover Problem which was one of Karp's 21 NP-complete problems [8] (see also [5]). A vertex cover of a graph is a set of vertices such that each edge of the graph is incident with at least one vertex of the set. The Vertex Cover Problem is the following decision problem.

Vertex Cover Problem (VCP).

Instance: A non-empty graph G, and a positive integer k. Question: Does G have a vertex cover of size at most k?

2. Hop Independent Dominating Problem

Consider the following decision problem:

Hop Independent Dominating Problem (HIDP).

Instance: A non-empty graph G, and a positive integer k.

Question: Does G have a hop independent dominating set of size at most k?

We show that the decision problem for HIDF is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Theorem 2.1. HIDP is NP-complete for planar bipartite graphs.

Proof. Clearly, the HIDP is NP, since it is easy to verify a "yes" instance of the HIDP in polynomial time. Now let us show how to transform the vertex cover problem to the HIDP so that one of them has a solution if and only if the other has a solution.

Let G be a connected planar bipartite graph of order \(n_G\) and size \(m_G \geq 2\). Let H be the graph obtained from G as follows. For each edge \(e = uv \in E(G)\), we subdivide the edge e three times. Let \(x_e, y_e, z_e\) be the subdivided vertices that were produced by subdividing e, where u is adjacent to \(x_e\), v is adjacent to \(z_e\), and \(y_e\) is adjacent to both \(x_e\) and \(z_e\). For every vertex \(v \in V(G) \cup \{x_e, z_e \mid e \in E(G)\}\) we add a \(P_5\)-path \(P_5^v : v_1v_2...v_5\), and join \(v_3\) to v, and then subdivide the edge \(v_3v\) two times. Let \(x_v\) and \(y_v\) be the subdivided vertices that were produced by subdividing the edge \(v_3v\) two times, where \(x_v\) is adjacent \(v_3\) and \(y_v\) is adjacent to v. For every vertex \(v \in \{y_e \mid e \in E(G)\}\) we add a \(P_5\)- path \(P_5^v : v_1v_2...v_5\) and join \(v_3\) to v, and subdivide the edge \(v_3v\) three times. Let \(x_v, y_v, z_v\) be the subdivided vertices that were produced by subdividing the edge \(v_3v\) three times, where \(x_v\) is adjacent to \(v_3\), \(v_3\) is adjacent to \(v_3\), and \(v_4\) is adjacent to both \(v_4\) and \(v_4\). Finally for each edge \(v_4\) end \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to both \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacent to \(v_4\) and \(v_4\) is adjacen

We show that G has a vertex cover of size at most k if and only if H has an HIDS of size at most \(k + 2n_G + 6m_G\). Assume first that G has a vertex cover, \(S_G\), of size at most k. Let

\[S_H = S_G \cup \{v_3, v_4 \mid v \in S_G\} \cup \{x_v, v_3 \mid v \in ((V(G) - S_G) \cup \{x_e, z_e, y_e \mid e \in E(G)\})\}.\]

Figure 1. The graphs G and H in the proof of Theorem 2.1.

Clearly \(d(a,b) \neq 2\) for any pair \(a,b \in S_H\). We show \(S_H\) is an HIDS of size at most \(k+2n_G+6m_G\). Clearly any vertex in \(\{y_e,y'_e,y''_e:e\in E(G)\}\) is hop dominated by \(S_G\). For any vertex \(v\in S_G\), any vertex in \(\{v_1,v_2,...,v_5\}\cup \{x_v,y_v\}\) is hop dominated by \(\{v_3,v_4\}\). For any vertex \(v\in V(G)-S_G\), any vertex in \(\{v_1,v_2,...,v_5\}\cup \{x_v,y_v,v\}\) is hop dominated by \(\{v_3,x_v\}\). For any edge \(e\in E(G)\), any vertex in \(\{y_{e_1},y_{e_2},...,y_{e_5}\}\cup \{x_{y_e},y_{y_e},z_{y_e}\}\) is hop dominated by \(\{y_{e_3},x_{y_e}\}\). For any edge \(e\in E(G)\), any vertex in \(\{x_{e_1},x_{e_2},...,x_{e_5}\}\cup \{x_{x_e},y_{x_e},x_e\}\) is hop dominated by \(\{x_{e_3},x_{x_e}\}\). Finally, for any edge \(e\in E(G)\), any vertex in \(\{z_{e_1},z_{e_2},...,z_{e_5}\}\cup \{x_{z_e},y_{z_e},z_e\}\) is hop dominated by \(\{z_{e_3},x_{z_e}\}\). Consequently, \(S_H\) is an HIDS of size at most \(k+2n_G+6m_G\).

Assume now that H has an HIDS, \(S_H\), of size at most \(k+2n_G+6m_G\). It is evident that for any vertex \(v \in V(G) \cup \{x_e, z_e, y_e \mid e \in E(G)\}\), \(|S_H \cap \{v_1, v_5, v_3\}| \geq 1\), and for any vertex \(v \in V(G) \cup \{x_e, z_e, y_e \mid e \in E(G)\}\), \(|S_H \cap \{v_2, v_4, x_v\}| \geq 1\). Furthermore, for every edge \(e = uv \in E(G)\), we have \(S_H \cap \{\{v, u, y_e, y_e', y_e''\} \cup \{y_v \mid v \in \{x_e, z_e, y_e \mid e \in E(G)\}\}\} \neq \emptyset\). If \(S_H \cap \{v, u\} = \emptyset\) for some edge \(e = uv \in E(G)\), then we remove one vertex of \(S_H \cap \{\{y_e, y_e', y_e''\} \cup \{y_v \mid v \in \{x_e, z_e, y_e \mid e \in E(G)\}\}\}\) and add precisely one of the vertices u or v to \(S_H\). Thus we may assume that \(S_H \cap \{v, u\} \neq \emptyset\) for any edge \(e = uv \in E(G)\). Thus \(S_G = S_H \cap V(G)\) is a vertex cover for G of size at most \(|S_H| - 2n_G - 6m_G\). Therefore G has a vertex cover of size at most k.

Theorem 2.2. HIDP is NP-complete for planar chordal graphs.

Proof. Clearly, the HIDP is in NP. Now let us show how to transform the vertex cover problem to the HIDP so that one of them has a solution if and only if the other has a solution.

Let G be a planar chordal graph of order \(n_G\) and size \(m_G \geq 2\). Let H be the graph obtained from G as follows: We replace every edge \(e = vu \in E(G)\) with a double edge e' = uv and e'' = uv. Then we subdivide each of e' and e'' three times. Let \(x_{e'}, y_{e'}, z_{e'}\) be the vertices that produced from subdividing the edge e', and \(x_{e''}\) are adjacent to u, \(z_{e'}\) and \(z_{e''}\) are adjacent to v, v, v, v, v, v, v, v,

We show that G has a vertex cover of size at most k if and only if H has an HIDS of size at most \(k + 2n_G + 12m_G\). Assume first that G has a vertex cover, \(S_G\), of size at most k. Let

\[S_H = S_G \cup \{v_3, v_4 \mid v \in S_G\} \cup \{v_3, x_v \mid v \in ((V(G) - S_G) \cup \{x_{e'}, x_{e''}, z_{e'}, z_{e''}, y_{e'}, y_{e''} \mid e \in E(G)\})\}.\]

Clearly \(d(a,b) \neq 2\) for any pair \(a,b \in S_H\). We show \(S_H\) is an HIDS of size at most \(k+2n_G+12m_G\). Clearly any vertex in \(\{y_{e'},y_{e''}:e\in E(G)\}\) is hop dominated by \(S_G\). For

Figure 2. The graphs G and H in the proof of Theorem 2.2.

any vertex \(v \in S_G\), any vertex in \(\{v_1, v_2, ..., v_5\} \cup \{x_v, y_v\}\) is hop dominated by \(\{v_3, v_4\}\). For any vertex \(v \in V(G) - S_G\), any vertex in \(\{v_1, v_2, ..., v_5\} \cup \{x_v, y_v, v\}\) is hop dominated by \(\{v_3, x_v\}\). For any edge \(e \in E(G)\), any vertex in \(\{y_{e'1}, y_{e'2}, ..., y_{e'5}\} \cup \{x_{y_{e''}}, y_{y_{e''}}, z_{y_{e''}}\}\) is hop dominated by \(\{y_{e'3}, x_{y_{e''}}\}\), and any vertex in \(\{y_{e''1}, y_{e''2}, ..., y_{e''5}\} \cup \{x_{y_{e''}}, y_{y_{e''}}, z_{y_{e''}}\}\) is hop dominated by \(\{y_{e''3}, x_{y_{e''}}\}\). For any edge \(e \in E(G)\), any vertex in \(\{x_{e''1}, x_{e'2}, ..., x_{e'5}\} \cup \{x_{x_{e''}}, y_{x_{e''}}, x_{e''}\}\) is hop dominated by \(\{x_{e''3}, x_{x_{e''}}\}\), and any vertex in \(\{x_{e''1}, x_{e''2}, ..., x_{e''5}\} \cup \{x_{x_{e''}}, y_{x_{e''}}, x_{e''}\}\) is hop dominated by \(\{x_{e''3}, x_{x_{e''}}\}\). For any edge \(e \in E(G)\), any vertex in \(\{z_{e'1}, z_{e'2}, ..., z_{e'5}\} \cup \{x_{z_{e''}}, y_{z_{e''}}, z_{e'}\}\) is hop dominated by \(\{z_{e''3}, x_{z_{e''}}\}\), and any vertex in \(\{z_{e''1}, z_{e''2}, ..., z_{e''5}\} \cup \{x_{z_{e''}}, y_{z_{e''}}, z_{e''}\}\) is hop dominated by \(\{z_{e''3}, x_{z_{e''}}\}\), and any vertex in \(\{z_{e''1}, z_{e''2}, ..., z_{e''5}\} \cup \{x_{z_{e''}}, y_{z_{e''}}, z_{e''}\}\) is hop dominated by \(\{z_{e''3}, x_{z_{e''}}\}\), and any vertex in \(\{z_{e''1}, z_{e''2}, ..., z_{e''5}\} \cup \{x_{z_{e''}}, y_{z_{e''}}, z_{e''}\}\) is hop dominated by \(\{z_{e''3}, x_{z_{e''}}\}\). Consequently, \(S_H\) is a hop independent dominating set of size at most \(k + 2n_G + 12m_G\).

Assume now that H has an HIDS, \(S_H\), of size at most \(k + 2n_G + 12m_G\). It is evident that for any vertex \(v \in V(G) \cup \{x_{e'}, x_{e''}, z_{e'}, z_{e''}, y_{e'}, y_{e''} \mid e \in E(G)\}, |S_H \cap \{v_1, v_5, v_3\}| \geq 1\), and for any vertex \(v \in V(G) \cup \{x_{e'}, x_{e''}, z_{e'}, z_{e''}, y_{e'}, y_{e''} \mid e \in E(G)\}, |S_H \cap \{v_2, v_4, x_v\}| \geq 1\). Furthermore, for every edge \(e = uv \in E(G)\), we have \(S_H \cap (\{v, u, y_{e''}, y_{e'}\} \cup \{y_v \mid v \in \{x_{e'}, x_{e''}, z_{e''}, y_{e'}, y_{e'}, y_{e''} \mid e \in E(G)\}\} \cup \{z_{y_{e'}}, z_{y_{e''}} : e \in E(G)\}) \neq \emptyset\). If \(S_H \cap \{v, u\} = \emptyset\) for some edge \(e = uv \in E(G)\), then we remove one vertex of \(S_H \cap (\{y_{e''}, y_{e'}\} \cup \{y_v \mid v \in E(G)\})\)

\(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\) and add precisely one of the vertices u or v to \(S_H\). Thus we may assume that \(S_H \cap \{v, u\} \neq \emptyset\), for any edge \(e = uv \in E(G)\). Thus \(S_G = S_H \cap V(G)\) is a vertex cover for G of size at most \(|S_H| - 2n_G - 12m_G\). Therefore G has a vertex cover of size at most k. \(\square\)

3. Hop Roman Dominating Function Problem

We next study the complexity issue of the hop Roman domination function problem. Consider the following decision problem:

Hop Roman Dominating Function Problem (HRDFP).

Instance: A non-empty graph G, and a positive integer k.

Question: Does G have a hop Roman dominating function of weight at most k?

We show that the decision problem for the HRDFP is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Theorem 3.1. HRDFP is NP-complete for planar bipartite graphs.

Proof. Clearly, the HRDFP is in NP, since it is easy to verify a "yes" instance of the HRDFP in polynomial time. Now let us show how to transform the vertex cover problem to the HRDFP so that one of them has a solution if and only if the other one has a solution.

Let G be a connected planar bipartite graph of order \(n_G\) and size \(m_G \geq 2\), and let H be the graph obtained from G as follows: We convert each edge \(e = vu \in E(G)\) into a triple-edge \(e_1 = vu\), \(e_2 = vu\) and \(e_3 = vu\), and then subdivide each of edges \(e_1\), \(e_2\) and \(e_3\) three times. Let the vertices \(x_{e_i}\), \(y_{e_i}\), \(z_{e_i}\) be the vertices that were produced from subdividing the edge \(e_i\), for i = 1, 2, 3, where the vertex \(x_{e_i}\) is adjacent to v, the vertex \(z_{e_i}\) is adjacent to u and \(d(y_{e_i}, u) = d(y_{e_i}, v) = 2\), for i = 1, 2, 3. For each edge \(e = vu \in E(G)\) we add a new vertex \(e_{vu}\) and a \(P_5\)-path \(P_5^v : v_1^e v_2^e ... v_5^e\), and join the vertex \(e_{vu}\) to u, v and \(v_3^e\). The resulting graph H has order \(n_H = n_G + 15m_G\) and size \(m_H = 19m_G\). Figure 3 illustrates the graph H if G is a path \(P_3\). We note that since G is connected and planar, so H is connected and planar. Further, by construction, H is bipartite. Thus, H is a connected planar bipartite graph.

We show that G has a vertex cover of size at most k if and only if H has an HRDF of weight \(2k + 4m_G\). Assume first that G has a vertex cover, \(S_G\), of size at most k. Let

\[S_H = S_G \cup \bigcup_{e=uv \in E(G)} \{v_3^e, e_{vu}\}.\]

We show that \(f = (V(H) - S_H, \emptyset, S_H)\) is an HRDF for H of weight at most \(2k + 4m_G\). For every edge \(e = vu \in E(G)\), the vertex \(v_3^e\) hop Roman dominates the vertices \(v_1^e\), \(v_5^e\), u and v in H, while the vertex \(e_{vu}\) hop Roman dominates the vertices \(v_2^e\), \(v_4^e\) and the neighbors of u and v in H. For any \(e \in E(G)\), since \(S_G\) is a vertex cover in G, the vertices \(y_{e_1}\), \(y_{e_2}\) and \(y_{e_3}\), are hop Roman dominated by \(S_G\) in H. Therefore, the function f is an HRDF for H of weight at most \(2k + 4m_G\).

Assume next that \(f = (V_0^f, V_1^f, V_2^f)\) is an HRDF for H of weight \(2k + 4m_G\). Without loss of generality we assume that f is a \(\gamma_{hR}\)-function of H.

Figure 3. The graph G and H in the proof of Theorem 3.1.

If for an edge \(e \in E(G)\), \(f(v_1^e) + f(v_3^e) + f(v_5^e) \le 1\), then \(v_1^e\) or \(v_5^e\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_1^e) + f(v_3^e) + f(v_5^e) \ge 2\) for every edge \(e \in E(G)\). If for an edge \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(e_{vu}) \le 1\), then \(v_2^e\) or \(v_4^e\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_2^e) + f(v_4^e) + f(e_{vu}) \ge 2\) for every edge \(e \in E(G)\).

If for some edge \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(e_{vu}) \ge 3\), then function g defined by \(g(v_2^e) = 0\), \(g(v_4^e) = 0\), \(g(e_{vu}) = 2\) and g(v) = f(v) otherwise, is an HRDF for H of weight less than \(\gamma_{hR}(H)\), a contradiction. Thus, for every \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(e_{uv}) = 2\). Similarly we can show that \(f(v_1^e) + f(v_3^e) + f(v_5^e) = 2\) for every edge \(e \in E(G)\).

If there exists an edge \(e \in E(G)\) such that \(f(z_{e_i}) > 0\) or \(f(x_{e_i}) > 0\), for some i = 1, 2, 3, then the function g defined by \(g(v_2^e) = g(v_4^e) = 0\), \(g(e_{vu}) = 2\), \(g(z_{e_i}) = g(x_{e_i}) = 0\) for each i = 1, 2, 3, and g(z) = f(z) otherwise, is an HRDF for H of weight g(V) < f(V), a contradiction. Thus, for every \(e \in E(G)\), \(f(z_{e_i}) = f(x_{e_i}) = 0\), for each i = 1, 2, 3.

If there exists an edge \(e=uv\in E(G)\) such that \(f(y_{e_i})>0\) for each i=1,2,3, then the function g defined by \(g(y_{e_1})=g(y_{e_2})=g(y_{e_3})=0\), g(u)=2 and g(z)=f(z) otherwise, is an HRDF with g(V)< f(V), a contradiction. Thus, for every edge \(e=uv\in E(G)\) there exists an integer \(i\in\{1,2,3\}\) such that \(f(y_{e_i})=0\). Since \(y_{e_i}\) is hop Roman dominated by f, we obtain that f(v)=2 or f(v)=2. Then we can see that \(f(y_{e_j})=0\) for each f(v)=1 for each f(v)=1 for every edge f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for each f(v)=1 for

Theorem 3.2. HRDFP is NP-complete for planar chordal graphs.

Proof. Clearly, the HRDFP is in NP. Now let us show how to transform the vertex cover problem

Figure 4. The graphs G and H in the proof of Theorem 3.2.

to the HRDFP so that one of them has a solution if and only if the other has a solution.

Let G be a connected planar chordal graph of order \(n_G\) and size \(m_G \geq 2\). Let H be the graph obtained from G as follows. For each edge \(e = uv \in E(G)\) we add two new vertices \(x^e\) and \(y^e\) and join each of them to both u and v. We then add three leaves \(x_1^e\), \(x_2^e\) and \(x_3^e\) to \(x^e\). We next add a \(P_5\)-path \(v_1^e v_2^e v_3^e v_4^e v_5^e\), and join \(v_3^e\) to \(y^e\). The resulting graph H has order \(n_H = n_G + 10m_G\) and size \(m_H = 13m_G\). Figure 4 illustrates the graph H if G is a cycle \(C_3\).

We show that G has a vertex cover of size at most k if and only if H has an HRDF of weight at most \(2k + 4m_G\). Assume first that G has a vertex cover, \(S_G\), of size at most k. Let

\[S_H = S_G \cup \bigcup_{e=uv \in E(G)} \{v_3^e, y^e\}.\]

For every edge \(e = uv \in E(G)\), the vertex \(v_3^e\) hop dominates the vertices \(v_1^e\), \(v_5^e\), u and v in H, while the vertex \(y^e\) hop dominates the vertices \(v_2^e\), \(v_4^e\) and \(x^e\). Since \(S_G\) is a vertex cover in G, for any edge \(e \in E(G)\), the vertices \(x_1^e\), \(x_2^e\) and \(x_3^e\) are hop dominated by \(S_G\). Therefore, the set \(S_H\) is an HDS for G and \(f = (V(H) - S_H, \emptyset, S_H)\) is a HRDF of weight at most \(2k + 4m_G\) for H.

Assume next that \(f = (V_0^f, V_1^f, V_2^f)\) is an HRDF for H of weight at most \(2k + 4m_G\). Without loss of generality, we may assume that f is a \(\gamma_{hR}(H)\)-function. If for an edge \(e \in E(G)\), \(f(v_1^e) + f(v_3^e) + f(v_5^e) \le 1\), then \(v_1^e\) or \(v_5^e\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_1^e) + f(v_3^e) + f(v_5^e) \ge 2\) for every edge \(e \in E(G)\). If for an edge \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(y^e) \le 1\), then \(v_2^e\) or \(v_4^e\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_2^e) + f(v_4^e) + f(y^e) \ge 2\) for every edge \(e \in E(G)\).

If for an edge \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(y^e) \ge 3\), then the function g defined by \(g(v_2^e) =\)

\(g(v_4^e) = 0, g(y^e) = 2\) and g(v) = f(v) otherwise, is an HRDF with g(V) < f(V), a contradiction. Thus, for every \(e \in E(G)\), \(f(v_2^e) + f(v_4^e) + f(y^e) = 2\). Also, we can show that for every \(e \in E(G)\), \(f(v_1^e) + f(v_3^e) + f(v_3^e) = 2\).

If there exists an edge \(e=uv\in E(G)\) such that \(f(x_i^e)>0\) for each i=1,2,3, then the function g defined by \(g(x_i^e)=0\) for each i=1,2,3, g(u)=2, and g(z)=f(z) otherwise, is an HRDF with g(V)< f(V), a contradiction. Thus, for every edge \(e=uv\in E(G)\), there exists an integer \(i\in\{1,2,3\}\) such that \(f(x_i^e)=0\). If for an edge \(e\in E(G),\) \(f(x_1^e)+f(x_2^e)+f(x_3^e)\geq 3\), then we can obtain an HRDF g with g(V)< f(V), a contradiction. Thus \(f(x_1^e)+f(x_2^e)+f(x_3^e)\leq 2\) for each \(e\in E(G)\).

For any \(e \in E(G)\) with \(f(x_1^e) + f(x_2^e) + f(x_3^e) = 0\), we have f(u) = 2 or f(v) = 2. Assume that \(f(x_1^e) + f(x_2^e) + f(x_3^e) > 0\) for some edge \(e \in E(G)\). Suppose that \(f(x_1^e) + f(x_2^e) + f(x_3^e) = 1\). Without loss of generality, assume that \(f(x_1^e) = 1\). Then f(u) = 2 or f(v) = 2, and so we can change \(f(x_1^e)\) to 0, to obtain an HRDF with weight less than \(\gamma_{hR}(H)\), a contradiction by the choice of f. Thus \(f(x_1^e) + f(x_2^e) + f(x_3^e) > 1\), and so \(f(x_1^e) + f(x_2^e) + f(x_3^e) = 2\). As before, we can see that \(f(x_i^e) \neq 1\) for i = 1, 2, 3. Therefore, there exists an integer \(i \in \{1, 2, 3\}\) such that \(f(x_i^e) = 2\). Then f(u) = f(v) = 0. Now we replace \(x_i^e\) with u or v in \(V_2^f\). We conclude that \(S_G = V_2^f \cap V(G)\) is a vertex cover of G of size at most \(\frac{1}{2}(\gamma_{hR}(H) - 4m_G)\). Thus, G has a vertex cover of size at most k.

4. Hop Roman Independent Dominating Function Problem

We next study the complexity issue of the hop Roman independent domination function problem. Consider the following decision problem:

Hop Roman Independent Dominating Function Problem (HRIDFP).

Instance: A non-empty graph G, and a positive integer k.

Question: Does G have a hop Roman independent dominating function of weight at most k?

We show that the decision problem for HRIDFP is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.

Theorem 4.1. HRIDFP is NP-complete for planar bipartite graphs.

Proof. Let G be a graph of order \(n_G\) and size \(m_G\), and let H be the connected planar bipartite graph constructed in the proof of Theorem 2.1. We show that G has a vertex cover of size at most k if and only if H has an HRIDF of weight at most \(2k + 4n_G + 12m_G\). Assume that G has a vertex cover, \(S_G\), of size at most k. Let \(f = (V(H) - S_H, \emptyset, S_H)\), where \(S_H\) is the HIDS constructed in the proof of Theorem 2.1. Then f is an HRIDF for H of weight \(2k + 4n_G + 12m_G\). Therefore, H has an HRIDF of weight at most \(2k + 4n_G + 12m_G\).

Assume next that \(f=(V_0^f,V_1^f,V_2^f)\) is an HRIDF in H of weight at most \(2k+4n_G+12m_G\). We show that G has a vertex cover of size at most k. Without loss of generality, we may assume that f is a \(\gamma_{hRI}(H)-\) function. If for a vertex \(v\in V(G)\cup \{x_e,z_e,y_e\mid e\in E(G)\},\ f(v_1)+f(v_3)+f(v_5)\leq 1\), then \(v_1\) or \(v_5\) is not hop Roman dominated by f, a contradiction. Therefore,

\(f(v_1)+f(v_3)+f(v_5)\geq 2 \text{ for any vertex of } V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}. \text{ If for a vertex } v\in V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}, \ f(v_2)+f(v_4)+f(x_v)\leq 1, \text{ then } v_2 \text{ or } v_4 \text{ is not hop Roman dominated by } f\text{, a contradiction. Therefore, } f(v_2)+f(v_4)+f(x_v)\geq 2 \text{ for any vertex of } V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}. \text{ If for a vertex of } V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}, \ f(v_2)+f(v_4)+f(x_v)\geq 3, \text{ then the function } g\text{ defined by } g(v_2)=g(v_4)=0, g(x_v)=2 \text{ and } g(v)=f(v) \text{ otherwise, is an HRDF with } g(V)< f(V), \text{ a contradiction. Thus, for any vertex of } V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}, \ f(v_2)+f(v_4)+f(x_v)=2. \text{ Also, we can show that for any vertex of } V(G)\cup \left\{x_e,z_e,y_e\mid e\in E(G)\right\}, \ f(v_1)+f(v_3)+f(v_5)=2.\)

If there exists an edge \(e=uv\in E(G)\) such that \(f(y_e)>0\), \(f(y_e')>0\) and \(f(y_e'')>0\), then the function g defined by \(g(y_e)=g(y_e')=g(y_e'')=0\), g(u)=2 and g(v)=f(v) otherwise, is an HRDF with g(V)< f(V), a contradiction. Thus, for every edge \(e=uv\in E(G)\), there exist at least one vertex \(v\in\{y_e,y_e',y_e''\}\) such that f(v)=0. If for an edge \(e\in E(G)\), \(f(y_e)+f(y_e')+f(y_e')+f(y_e'')\geq 3\), then there exists an HRDF g with g(V)< f(V), a contradiction. Thus \(f(y_e)+f(y_e')+f(y_e'')\leq 2\) for each \(e\in E(G)\). For any \(e\in E(G)\) with \(f(y_e)+f(y_e')+f(y_e'')=0\), we have f(u)=2 or f(v)=2. Assume that \(f(y_e)+f(y_e')+f(y_e'')>0\) for some edge \(e\in E(G)\). Suppose that \(f(y_e)+f(y_e')+f(y_e'')=1\). Without loss of generality, assume that \(f(y_e)=1\). Then f(u)=2 or f(v)=2, and so we can change \(f(y_e)\) to 0, to obtain an HRIDF with weight less than \(\gamma_{hRI}(H)\), a contradiction by the choice of f. Thus, \(f(y_e)+f(y_e')+f(y_e'')>1\), and so \(f(y_e)+f(y_e')+f(y_e'')=2\). As before, we can see that \(f(y_e)\neq 1\), \(f(y_e)\neq 1\) and \(f(y_e'')\neq 1\). Therefore, there exist a vertex \(z\in\{y_e,y_e',y_e''\}\) such that f(z)=2. Then f(u)=0 and f(v)=0. Without loss of generality, assume that \(f(y_e)=2\). Now replace \(y_e\) with \(y_e=1\) or \(y_e=1\). We conclude that \(y_e=1\) or \(y_e=1\) is a vertex cover of \(y_e=1\) or \(y_e=1\). Thus, \(y_e=1\) is a vertex cover of \(y_e=1\). Thus, \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\). Thus, \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\). Thus, \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\). Thus, \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is a vertex cover of \(y_e=1\) is an indepth \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=1\) in \(y_e=\)

Theorem 4.2. HRIDFP is NP-complete for planar chordal graphs.

Proof. Let G be a graph of order \(n_G\) and size \(m_G\), and let H be the connected planar chordal graph constructed in the proof of Theorem 2.2. We show that G has a vertex cover of size at most k if and only if H has an HRIDF of weight at most \(2k + 4n_G + 24m_G\). Assume that G has a vertex cover, \(S_G\), of size at most k. Let \(f = (V(H) - S_H, \emptyset, S_H)\), where \(S_H\) is the HIDS constructed in the proof of Theorem 2.2. Then f is an HRIDF for H of weight \(2k + 4n_G + 24m_G\). Therefore, H has an HRIDF of weight at most \(2k + 4n_G + 24m_G\).

Assume next that \(f=(V_0^f,V_1^f,V_2^f)\) is an HRIDF for H of weight at most \(2k+4n_G+24m_G\). We show that G has a vertex cover of size at most k. Without loss of generality, we may assume that f is a \(\gamma_{hRI}(H)-\) function. If for a vertex \(v\in V(G)\cup\{x_{e'},z_{e'},x_{e''},z_{e''},y_{e''}\mid e\in E(G)\}, f(v_1)+f(v_3)+f(v_5)\leq 1\), then \(v_1\) or \(v_5\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_1)+f(v_3)+f(v_5)\geq 2\) for any vertex of \(V(G)\cup\{x_{e'},z_{e'},x_{e''},z_{e''},y_{e''}\mid e\in E(G)\}\). If for a vertex \(v\in V(G)\cup\{x_{e'},z_{e'},x_{e''},z_{e''},y_{e''}\mid e\in E(G)\}, f(v_2)+f(v_4)+f(x_v)\leq 1\), then \(v_2\) or \(v_4\) is not hop Roman dominated by f, a contradiction. Therefore, \(f(v_2)+f(v_4)+f(x_v)\geq 2\) for any vertex of \(V(G)\cup\{x_{e'},z_{e'},x_{e''},z_{e''},y_{e''},y_{e''}\mid e\in E(G)\}\). If \(f(v_2)+f(v_4)+f(x_v)\geq 3\), then the function g defined by \(g(v_2)=g(v_4)=0, g(x_v)=2\) and g(v)=f(v) otherwise, is an HRIDF for H implying that g(V)< f(V), a contradiction. Thus, for any vertex of \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

For any vertex \(z \in \{y_v \mid v \in \{x_{e'}, z_{e'}, x_{e''}, z_{e''}, y_{e''}, y_{e''} \mid e \in E(G)\}\}, f(z) = 0\), since otherwise we can find an HRIDF g with g(V) < f(V), a contradiction. Similarly for any vertex \(z \in \{z_v \mid v \in \{y_{e'}, y_{e''} \mid e \in E(G)\}\}, f(z) = 0.\) If for an edge \(e = uv \in E(G), f(u) + 1\)\(f(y_{e'}) + f(y_{e''}) \le 1\) and \(f(v) + f(y_{e'}) + f(y_{e''}) \le 1\), then \(y_{e'}\) or \(y_{e''}\) is not hop Roman dominated by f, a contradiction. Thus for any edge \(e = uv \in E(G)\), either \(f(u) + f(y_{e'}) + f(y_{e''}) \ge 2\)or \(f(v) + f(y_{e'}) + f(y_{e''}) \ge 2\). If for an edge \(e = uv \in E(G)\), \(f(u) + f(y_{e'}) + f(y_{e''}) \ge 3\) or \(f(v) + f(y_{e'}) + f(y_{e''}) \ge 3\), then there exists a function g with g(V) < f(V), a contradiction. Thus for every edge \(e \in E(G)\), \(f(u) + f(y_{e'}) + f(y_{e''}) \le 2\) and \(f(v) + f(y_{e'}) + f(y_{e''}) \le 2\). Since for any edge \(e = uv \in E(G)\), either \(f(u) + f(y_{e'}) + f(y_{e''}) \ge 2\) or \(f(v) + f(y_{e'}) + f(y_{e''}) \ge 2\), we deduce that for any edge \(e = uv \in E(G)\), either \(f(u) + f(y_{e'}) + f(y_{e''}) = 2\) or \(f(v) + f(y_{e''}) + f(y_{e''}) = 2\). Since for every edge \(e \in E(G)\), \(d(y_{e'}, y_{e''}) = 1\), we have \(f(y_{e'}) \neq 2\) and \(f(y_{e''}) \neq 2\), and so either \(f(y_{e'}) = f(y_{e''}) = 1\) or \(f(y_{e'}) = f(y_{e''}) = 0\). For any edge \(e = uv \in E(G)\) with \(f(y_{e'}) = f(y_{e''}) = 0\) we have f(u) = 2 or f(v) = 2. Assume that \(f(y_{e'}) = f(y_{e''}) = 1\)for some edge \(e = uv \in E(G)\). Then f(u) = f(v) = 0, and we can change both \(f(y_{e'})\) and \(f(y_{e''})\) to 0 and one of f(u) or f(v) to 2 to obtain a \(\gamma_{hRI}(H)\)-function g such that g(u)=2 or g(v) = 2. We conclude that \(S_G = V_2^f \cap V(G)\) is a vertex cover for graph G of size at most \(\frac{1}{2}(\gamma_{hRI}(H) - 4n_G - 24m_G)\). Therefore, G has a vertex cover of size at most k.

References

• [1] S.K. Ayyaswamy, B. Krishnakumari, C. Natarajan and Y. B. Venkatakrishnan, Bounds on the hop domination number of a tree, Proceedings of Math. Sci., Indian Academy of Science (2015), DOI:10.1007/s12044-015-0251-6.
• [2] S.K. Ayyaswamy, C. Natarajan, Hop domination in Graphs, Discussiones Math. Graph The-ory (Submitted).
• [3] E.J. Cockayane, P.M. Dreyer Jr., S.M. Hedetniemi and S.T. Hedetniemi, On Roman domination in graphs, Discrete Math. 278 (2004), 11–22.
• [4] M. Farhadi Jalalvand and N. Jafari Rad, On the complexity of k-step and k-hop dominating sets in graphs, Math. Montisnigri 40 (2017), 36–41.
• [5] M.R. Garey, D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-completeness, Freeman, New York, 1979.
• [6] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc. New York, 1998.
• [7] M.A. Henning and N. Jarfari Rad, On 2-step and hop dominating sets in graphs, Graphs Combin. 33 (4) (2017), 913–927.
• [8] R.M. Karp, Reducibility among combinatorial problems, In R.E. Miller and J.W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. 85–103.

• [9] C. Natarajan and S.K. Ayyaswamy, Hop domination in graphs-II, An. Stt. Univ. Ovidius Constanta 23 (2) (2015), 187–199.
• [10] C.S. ReVelle, K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), 585–594.
• [11] E. Shabani, Hop Roman domination in graphs, Manuscript (2017).
• [12] I. Stewart, Defend the roman empire!, Sci. Amer. 281 (6) (1999), 136–139.