Degree equitable restrained double domination in graphs

Sunilkumar. M. Hosamani^a , Shailaja Shirkol^b , Preeti B. Jinagouda^b , Marcin Krzywkowski^c

sunilkumar.rcu@gmail.com, shailajashirkol@gmail.com, preetijinagouda@gmail.com, marcin.krzywkowski@gmail.com

A subset D ⊆ V (G) is called an equitable dominating set of a graph G if every vertex v ∈ V (G)\D has a neighbor u ∈ D such that |dG(u) − dG(v)| ≤ 1. An equitable dominating set D is a degree equitable restrained double dominating set (DERD-dominating set) of G if every vertex of G is dominated by at least two vertices of D, and hV (G) \ Di has no isolated vertices. The DERDdomination number of G, denoted by γ e cl(G), is the minimum cardinality of a DERD-dominating set of G. We initiate the study of DERD-domination in graphs and we obtain some sharp bounds. Finally, we show that the decision problem for determining γ e cl(G) is NP-complete.

Keywords: domination, degree equitable domination, DERD-domination

Mathematics Subject Classification : 05C69

DOI: 10.5614/ejgta.2021.9.1.10

1. Introduction

Let G = (V, E) be a graph. The number of vertices of G we denote by n and the number of edges we denote by m, thus |V (G)| = n and |E(G)| = m. The complement of G, denoted by G¯, is a graph which has the same vertices as G, and in which two vertices are adjacent if and

Received: 30 August 2017, Revised: 30 May 2019, Accepted: 27 December 2020.

^aDepartment of Mathematics, Rani Channamma University, Belagavi-591146, Karnataka State, India

^bDepartment of Mathematics, SDMCET, Dharwad, Karnataka, India

^cFaculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology, Poland

only if they are not adjacent in G. By the open neighborhood of a vertex v of G we mean the set NG(v) = {u ∈ V (G): uv ∈ E(G)}. By the closed neighborhood of a vertex v of G we mean the set NG[v] = NG(v) ∪ {v}. The degree of a vertex v, denoted by dG(v), is the cardinality of its open neighborhood. A vertex is called isolated if it has no neighbors, while it is called universal if it is adjacent to all other vertices. Let S be a subset of the set of vertices of G, and let u ∈ S. A vertex v is a private neighbor of u with respect to S if NG[v] ∩ S = {u}. The set of private neighbors of u with respect to S is the set pn[u, S] = {v : NG[v] ∩ S = {u}}. If u ∈ pn[u, S] and u is an isolated vertex in hSi, then u is called its own private neighbor. By a leaf we mean a vertex of degree one, while a support vertex is a vertex adjacent to a leaf. We say that a support vertex is weak if it is adjacent to exactly one leaf. We say that a vertex is isolated if it has no neighbor. Let ∆(G) mean the maximum degree among all vertices of G. The path (cycle, respectively) on n vertices we denote by Pⁿ (Cn, respectively). A wheel Wn, where n ≥ 4, is a graph with n vertices, formed by connecting a vertex to all vertices of a cycle Cn−1. The distance between two vertices of a graph is the number of edges in a shortest path connecting them. The eccentricity of a vertex is the greatest distance between it and any other vertex. The diameter of a graph G, denoted by diam(G), is the maximum eccentricity among all vertices of G. By Kp,q we denote a complete bipartite graph with partite sets of cardinalities p and q. By a star we mean the graph K1,q. By a double star we mean a graph obtained from a star by joining a positive number of vertices to one of its leaves. Generally, let K^t1,t2,...,t^k denote the complete multipartite graph with vertex set S¹ ∪ S² ∪ . . . ∪ Sk, where |Sⁱ | = tⁱ for positive integers i ≤ t.

A subset D ⊆ V (G) is a dominating set of G if every vertex of V (G) \ D has a neighbor in D. The domination number of G, denoted by γ(G), is the minimum cardinality of a dominating set of G. For a comprehensive survey of domination in graphs, see [4, 5].

A subset D ⊆ V (G) is a restrained dominating set of G if every vertex of V (G) \ D has a neighbor in D as well as a neighbor in V (G) \ D. The restrained domination number of G, denoted by γr(G), is the minimum cardinality of a restrained dominating set of G. A restrained dominating set of G of minimum cardinality is called a γr(G)-set.

A dominating set D of a graph G is said to be a cototal dominating set of G if the induced subgraph hV (G) \ Di has no isolated vertices. The cototal domination number of G, denoted by γcl(G), is the minimum cardinality of a cototal dominating set of G. Restrained domination in graphs was introduced by Domke et. al [1]. Independently, Kulli et. al [9] initiated the study of cototal domination in graphs. The concepts of restrained domination and cototal domination are equivalent.

A subset D ⊆ V (G) is a double dominating set of G if every vertex of G is dominated by at least two vertices of D. The double domination number of G, denoted by γd(G), is the minimum cardinality of a double dominating set of G. The study of double domination in graphs was initiated by Harary and Haynes [3].

A subset D ⊆ V (G) is a restrained double dominating set of G if every vertex of G is dominated by at least two vertices of D, and no vertex of hV (G) \ Di is isolated. The restrained double domination number of G, denoted by γdcl(G), is the minimum cardinality of a restrained double dominating set of G. The study of restrained double domination in graphs was initiated by in [8].

A subset D ⊆ V (G) is called an equitable dominating set of G if every vertex v ∈ V (G) \ D has a neighbor u ∈ D such that |dG(u) − dG(v)| ≤ 1. The equitable domination number of G, denoted by γ e (G), is the minimum cardinality of an equitable dominating set of G. The concept of equitable domination in graphs was introduced by V. Swaminathan and K. Dharmalingam [11] by considering the following real world situation. In a network, nodes with nearly equal capacity may interact with each other in a better way. In societies, persons with nearly equal statuses tend to be friendly. For more details on the domination refer [6, 7, 10, 12].

We introduce a new variant of equitable domination, namely the degree equitable restrained double domination (DERD-domination), and we initiate the study of this parameter. An equitable dominating set D of a graph G is said to be a DERD-dominating set of G if every vertex of G is dominated by at least two vertices of D, and hV (G) \ Di has no isolated vertices. The DERDdomination number of G, denoted by γ e cl(G), is the minimum cardinality of a DERD-dominating set of G.

2. Results

Since the one-vertex graph, as well as all graphs with an isolated vertex, does not have a DERD-dominating set, in this paper we consider only graphs without isolated vertices.

We begin with the following straightforward observations.

Observation 1. Let G be a graph without isolated vertices. Then every DERD-dominating set of G contains all leaves and support vertices of G.

Observation 2. There is no graph G such that γ e cl(G) = n − 1.

Observation 3. For every positive integer n we have

\[\gamma_{cl}^e(K_n) = \begin{cases} 3, & \text{if } n = 3; \\ 2, & \text{otherwise.} \end{cases}\]

Observation 4. For every integer n ≥ 2 we have γ e cl(Pn) = n.

Observation 5. If n ≥ 3 is an integer, then γ e cl(Cn) = n.

Observation 6. For every integer n ≥ 4 we have γ e cl(Wn) = bn/2c.

Observation 7. If m and n are positive integers, then

\[\gamma_{cl}^{e}(K_{m,n}) = \begin{cases} 4, & \text{if } |m-n| \le 1 \text{ and } 3 \le m \le n; \\ m+n, & \text{otherwise.} \end{cases}\]

We have the following property of regular and (k, k + 1)-biregular graphs.

Theorem 8. If a graph G is regular or(k, k+1)-biregular, for any integer k, then γ e cl(G) = γdcl(G).

Proof. Let D be a minimum restrained double dominating set of G. Let \(u \in V(G) \setminus D\). Thus there exist vertices \(w, v \in D\) such that \(uw, uv \in E(G)\). We have \(|d_G(u) - d_G(v)| \leq 1\) and \(|d_G(u) - d_G(w)| \leq 1\). Therefore D is a DERD-dominating set of G. Consequently, \(\gamma^e_{cl}(G) \leq |D| = \gamma_{dcl}(G)\). Obviously, \(\gamma_{dcl}(G) \leq \gamma^e_{cl}(G)\). This implies that \(\gamma^e_{cl}(G) = \gamma_{dcl}(G)\).

Theorem 9. For every graph G we have \(2 \le \gamma_{cl}^e(G) \le n\). Further, the lower bound is attained if and only if \(G = K_2\) or \(G = K_n - \{x\}\) where x is any vertex in \(K_n\); \(n \ge 5\) and the upper bound is attained if and only if G does not contain an edge \(uv \in E(G)\) which satisfies the following conditions:

• (i) there are vertices \(w \in N_G(u)\) and \(z \in N_G(v)\) such that \(|N_G(u)| \ge 3\) and \(|N_G(v)| \ge 3\);
• (ii) there are vertices \(w \in N_G(u)\) and \(z \in N_G(v)\) such that \(|d_G(u) d_G(w)| \le 1\) and \(|d_G(v) d_G(z)| \le 1\).

Proof. Lower bound follows from the definition of DERD-set. Now consider the equality of lower bound. Suppose \(\gamma^e_{cl}(G) = 2\) and \(G \neq K_n\) or \(K_n - \{x\}\). Then G contains at least two vertices \(u, v \in V(G)\) such that \(\langle \{u, v\} \rangle\) contains no edge. Let D be DERD-set of G such that \(u, v \notin D\). Let u and u are independent vertices in u and u and u are independent vertices in u and u and u are independent vertices in u and u and u also by the definition of DERD-set u contains no isolated vertices. Therefore, we need at least one more vertex to compliance the necessary conditions required to define DERD-set in u and u and u and u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u are independent vertices in u and u a

Conversely, suppose \(G=K_n\), then by Observation 3, \(\gamma^e_{cl}(G)=2\) and if \(G=K_n-\{x\}; n\geq 5\), then any two adjacent vertices will form a DERD-set for G. Hence \(\gamma^e_{cl}(G)=2\). Now consider the upper bound. Suppose \(\gamma^e_{cl}(G)=n\) and G contains an edge which satisfied the conditions in the hypothesis of the theorem, then \(V-\{w,z\}\) will form a DERD-set for G. Hence \(\gamma^e_{cl}(G)=|V-\{w,z\}|=n-2\). Hence G must not contain an edge as stated in the hypothesis of the theorem.

We now characterize the trees T such that \(\gamma_{cl}^e(T) = n\).

Theorem 10. Let T be a tree. We have \(\gamma_{cl}^e(T) = n\) if and only if T does not contain an edge \(uv \in E(T)\) which is incident to exactly four weak support vertices x, y, z, w such that \(N(x) \cap N(y) = \{u\}\) and \(N(z) \cap N(w) = \{v\}\).

Proof. Let T be a tree and \(\gamma^e_{cl}(T) = n\). Suppose T does not satisfies the hypothesis of the theorem, then there exist at least an edge \(uv \in E(T)\) incident to exactly four support vertices x, y, z, w such that \(N(x) \cap N(y) = \{u\}\) and \(N(z) \cap N(w) = \{v\}\) which implies that \(V - \{u, v\}\) is isomorphic to \(K_2\). Therefore |D| = n - 2. Hence \(\gamma^e_{cl}(T) = |D| = n - 2\), a contradiction.

Conversely, suppose G does not contain an edge \(uv \in E(T)\) as stated in the hypothesis of the theorem, then \(\langle V - D \rangle = \pi\), which implies that |D| = n. Hence \(\gamma_{cl}^e(T) = |D| = n\).

By Observation 2, there exists no graph with \(\gamma^e_{cl}(T) = n - 1\).

We now consider trees T such that \(\gamma_{cl}^e(T) \leq n-2\).

Let S(n,k)-star (where \(n \geq 2\) and \(k \geq 1\)) be a tree obtained from a path \(P_n\) making each vertex \(v_i \in V(P_n)\) (\(2 \leq i \leq n\)) adjacent to least k new leaves. We have |V(S(n,k))| = n + k and |E(S(n,k))| = n + k - 1.

Operation \(\mathcal{O}\): Let v be a support vertex of a tree T. Attach \(|d_G(v) - 1|\) or \(|d_G(v) - 2|\) leaves to at least one leaf adjacent to v, and attach exactly one leaf to other leaves adjacent to v.

Let \(\mathcal{T}\) be the family of trees such that

\(\mathcal{T} = \{T : T \text{ is obtained from a star by a finite sequence of operations } \mathcal{O}\}.\)

We now characterize the trees with \(\gamma_{cl}^e(T) = n - 2\).

Theorem 11. If T is a tree with at least six vertices, then \(\gamma_{cl}^e(T) = n - 2\) if and only if \(T \in \mathcal{T}\) and T is obtained from a S(2, k)-star \((k \ge 2)\) by a finite sequence of operations \(\mathcal{O}\).

Similarly, we can characterize the trees with \(\gamma_{cl}^e(T) = k\) \((k \ge 3)\) by S(n, n - k)-star by finite sequence of operations \(\mathcal{O}\).

We need the following theorem to prove our further results.

Theorem 12 ([4]). Let G be a graph without isolated vertices. Then \(\gamma(G) = n/2\) if and only if each component of G is a cycle \(C_4\) or \(G = H \circ K_1\), for any connected graph H.

Next we characterize the class of graphs with \(\gamma_{cl}^e(G) = 2\gamma(G)\).

Theorem 13. Let G be a graph without isolated vertices, and which is not a tree. Then \(\gamma_{cl}^e(G) = 2\gamma(G)\) if and only if each component of G is a cycle \(C_4\) or \(G = H \circ K_1\), for any connected graph H.

Proof. Let G be a graph without isolated vertices. Let D be a DERD-dominating set of G. If each component of G is a cycle \(C_4\), then by Theorem 12, \(\gamma(G) = \frac{n}{2}\) and by Observation 4, we have \(\gamma_{cl}^e(G) = n\). If \(G = H \circ K_1\), then \(\gamma_{cl}^e(G) = n\) as every vertex of \(H \circ K_1\) is a leaf or a support vertex. By Theorem 12 we have \(\gamma(G) = n/2\). Hence \(\gamma_{cl}^e(G) = n = n/2 + n/2 = \gamma(G) + \gamma(G) = 2\gamma(G)\).

3. Complexity issues for \(\gamma^e_{cl}(G)\)

To show that the DERD-domination decision problem for arbitrary graphs is NP-complete, we shall use a well known NP-completeness result called Exact Three Cover (X3C), which is defined as follows.

EXACT COVER BY 3-SETS (X3C).

Instance: A finite set X with |X| = 3m and a collection C of 3-element subsets of X.

Question: Does C contain an exact cover for X, that is, a subcollection \(C' \subseteq C\) such that every element of X occurs in exactly one member of C'? Note that if C' exists, then its cardinality is precisely m.

Theorem 14 ([2]). X3C is NP-complete.

DEGREE EQUITABLE RESTRAINED DOUBLE DOMINATING SET (DERDdominating set).

Instance: A graph G = (V, E) and a positive integer k ≤ |V |.

Question: Is there a DERD-dominating set of cardinality at most k?

Theorem 15. DERD-dominating set problem is NP-complete, even for bipartite graphs.

Proof. It is clear that the DERD-dominating set problem is NP. To show that it is NP-complete, we establish a polynomial transformation from X3C. Let X = {x1, x2, . . . , x3m} and C = {c1, c2, . . . , cm} be an arbitrary instance of X3C. We construct a bipartite graph G and a positive integer k such that this instance of X3C will have an exact 3-cover if and only if G has a DERD-dominating set of cardinality at most k. With each edge xⁱ ∈ X, associate a path P⁴ with vertices xⁱ , yⁱ , zⁱ , ti , with each c^j associate a path P³ with vertices c^j , d^j , s^j . Then add new vertices u1, u2, . . . , u2m, and make them adjacent to all x 0 j s. The construction of a bipartite graph G is completed by joining xⁱ and c^j if and only if xⁱ ∈ c^j . Finally, set k = 2m + 9m.

Assume that C has an exact 3-cover, say c 0 . Then

\[\bigcup_{1 \le i \le 3m} \{z_i, t_i\} \cup \bigcup_{1 \le j \le m} \{d_j, s_j\} \cup \{c_j; c_j \in c'\} \cup \bigcup_{1 \le j \le 2m} u_j\]

is a DERD-dominating set of G of cardinality 2m + 9m. This construction can clearly be determined in polynomial time.

Now assume that D is a DERD-dominating set of cardinality at most 2m + 9m. Then the vertices in the set L, defined by

\[\bigcup_{1 \le i \le 3m} \{z_i, t_i\} \cup \bigcup_{1 \le j \le m} \{d_j, s_j\}\]

are all leaves, and their neighbors have to be in D. Hence |D| − |L| ≤ (2m + 9m)−(2m + 6m) = 3m. Let I = {i ∈ (1, 2, . . . , 3m): xⁱ ∈ D or yⁱ ∈ D} and let J = {j ∈ (1, 2, . . . , 2m): c^j ∈ D or u^j ∈ D}. Then since D is a double dominating set of G, we have

\[\bigcup_{i \in I} \{x_i, y_i\} \cup \bigcup_{j \in J} N_G[c_j] \cup \bigcup_{j \in J} \{u_j\} \supseteq \{x_1, x_2, \dots, x_{3m}\}.\]

We conclude that |I|+3|J| ≥ 9m. Also |I|+|J| ≤ |D|−|L| ≤ 3m. Hence |3I|+3|J| ≤ |I|+3|J|, thus I = ∅. We conclude that xⁱ , yⁱ ∈/ D for i = 1, 2, . . . , 3m. Since xⁱ (i = 1, 2, . . . , 3m) is dominated by D, we conclude that |J| = 3m and c ⁰ = {c^j : j ∈ J} is an exact cover for X.

Acknowledgement

The authors are indebted to the referees for various valuable comments leading to improvements of the paper.

• [1] G. Domke, J. Hatting, S. Hedetniemi, R. Laskar, and L. Markus, Restrained domination in graphs, Discrete Math. 203 (2009), 61–69.
• [2] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.
• [3] F. Harary and T. Haynes, Double domination in graphs, Ars Combin. 55 (2000), 201–213.
• [4] T. Haynes, S. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
• [5] T. Haynes, S. Hedetniemi, and P.J. Slater (eds.), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
• [6] S.M. Hosseini Moghaddam, D.A. Mojdeh, B. Samadib, and L. Volkmann, On the signed 2-independence number of graphs, Electron. J. Graph Theory Appl. 5 (1) (2017), 36–42.
• [7] N. Jafari Rad, A note on the edge Roman domination in trees, Electron. J. Graph Theory Appl. 5 (1) (2017), 1–6.
• [8] R. Kala and T. Vasantha, Restrained double domination number of a graph, AKCE Int. J. Graphs Comb. 5 (2008), 73–82.
• [9] V. Kulli, B. Janakiram, and R. Iyer, The cototal domination number of a graph, J. Discrete Math. Sci. Cryptogr. 2 (1999), 179–184.
• [10] S.J. Seo and P.J. Slater, Open-independent, open-locating-dominating sets, Electron. J. Graph Theory Appl. 5 (2) (2017), 179–193.
• [11] V. Swaminathan and K. Dharmalingam, Degree equitable domination on graphs, Kragujevac Journal of Mathematics 35 (2011), 191–197.
• [12] E. Vatandoost and F. Ramezani, On the domination and signed domination numbers of zerodivisor graph, Electron. J. Graph Theory Appl. 4 (2) (2016), 148–156.