EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 3, 2024, 1539-1552 ISSN 1307-5543 – ejpam.com Published by New York Business Global Convex 2-Domination in Graphs Sergio R. Canoy , Jr.1,2, Ferdinand P. Jamil 1,2, Rona Jane G. Fortosa 1,2,∗, Jead M. Macalisang 1,2 1 Department of Mathematics and Statistics, College of Science and Mathematics, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Center of Mathematical and Theoretical Physical Sciences- PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. Let G be a connected graph. A set S ⊆ V (G) is convex 2-dominating if S is both convex and 2-dominating. The minimum cardinality among all convex 2-dominating sets in G, denoted by γ2con(G), is called the convex 2-domination number of G. In this paper, we initiate the study of convex 2- domination in graphs. We show that any two positive integers a and b with 6 ≤ a ≤ b are, respectively, realizable as the convex domination number and convex 2-domination number of some connected graph. Furthermore, we characterize the convex 2-dominating sets in the join, corona, lexicographic product, and Cartesian product of two graphs and determine the corresponding convex 2-domination number of each of these graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: convex, 2-dominating, convex 2-domination, join, corona, lexico- graphic product, Cartesian product 1. Introduction Domination is one of the well-studied concepts in Graph Theory. Variations of domina- tion as well as concepts related to it have been introduced and explored in various aspects and in several graphs (including those graphs resulting from binary operations). Two of its variants utilized the concepts of geodetic and convex sets. For studies that involve these concepts one may consider [5], [4], [9], and [22]. For some variations of domination, one may refer to [3], [10], [13], [20], [23] and [25]. Recently, motivated by some historical and theoretical applications, Roman and Italian domination concepts have also been studied (see [1], [2], [11], [12], [14], [16], [18], [21], [26], [27], and [28]). ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i3.5189 Email addresses: sergio.cano@g.msuiit.edu.ph (S. Canoy, Jr.), ferdinand.jamil@g.msuiit.edu.ph (F. Jamil), ronajane.fortosa@g.msuiit.edu.ph (RJ. Fortosa), jead.macalisang@g.msuiit.edu.ph (J. Macalisang) https://www.ejpam.com 1539 © 2024 EJPAM All rights reserved. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1540 One can readily observe that a variant of the domination concept is usually obtained by combining a domination concept with other graph-theoretic concepts. For example, convex domination is simply the combination of the standard domination and the notion of convexity in graphs (see [8], [17], and [24]). In this paper, the concept of convex 2- domination will be introduced and investigated. This new concept is a combination of convexity and 2-domination. As used to model a protection strategy problem in a given network, every vertex (location) which is not in a 2-dominating set will be considered unsafe (as it contains no guard). Hence, the elements of a 2-dominating set are the ones considered safe locations in the network and each location contains a guard. To defend or secure a given network, every unsafe location must be adjacent to at least two safe locations. This ensures that when an unsafe location is attacked, a location is within the vicinity of the guards from these safe locations. The convexity property attached to the concept guarantees that every location in any shortest path connecting two safe locations is also safe. This newly defined concept is useful when studying a variation of Italian domination, in particular, convex Italian domination [19]. 2. Terminologies and Notations For a connected graph G = (V (G), E(G) and vertices u and v of G, any shortest path joining u and v is called a u-v geodesic. The length of a u-v geodesic is the distance between u and v. This distance is denoted by dG(u, v). The set IG[u, v] consists of vertices u and v and those lying on any u-v geodesic. Here, IG(u, v) = IG[u, v] \ {u, v}. The set NG(u) is called the open neighborhood of u, i.e., NG(u) consists of all v ∈ V (G) such that uv ∈ E(G). The closed neighborhood of u is the set NG[u] = NG(u) ∪ {u}. If S ⊆ V (G), then NG(S) = ∪v∈SNG(v) and NG[S] = N(S) ∪ S. The degree of a vertex v, denoted by degG(v), is given by degG(v) = |N(v)|. A vertex of degree 1 is called an end-vertex or a leaf. If v is a leaf and w ∈ NG(v), then w is called a support vertex. A vertex v is an extreme or simplicial vertex in G if NG(v) induces a complete subgraph of G, that is, Ext(G) = {v ∈ V (G) : NG(v) induces a complete subgraph of G}. We denote by L(G), S(G), and Ext(G) the sets containing the leaves, the support, and the extreme vertices, respectively, of graph G. A set S ⊆ V (G) is non-connecting in G if for every two vertices x, y ∈ V (G) \ S with dG(x, y) = 2, it holds that NG(x) ∩NG(y) ∩ S = ∅. A set S ⊆ V (G) is independent if dG(x, y) ̸= 1 for every pair of distinct vertices x, y ∈ S. The set Ind(G) denotes the set of all vertices v of G such that NG(v) is an independent subset of V (G). Clearly, L(G) ⊆ Ind(G). A set S ⊆ V (G) is said to be dominating (resp. 2-dominating) in G if N [S] = V (G) (resp. |NG(v) ∩ S| ≥ 2 for every v ∈ V (G) \ S). The smallest cardinality of a dominating (resp. 2-dominating) set S is called the domination number (resp. 2-domination number) of G and is denoted by γ(G) (resp. γ2(G)). Any dominating (resp. 2-dominating) set with cardinality γ(G) (resp. γ2(G)) is called a γ-set (resp. γ2-set) in G. If {v} is a dominating set in G, then we call v a dominating vertex in G. A set S ⊆ V (G) is a clique if the graph ⟨S⟩ induced by S is a complete graph. A R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1541 set S ⊆ V (G) is clique dominating (resp. clique 2-dominating) if S is both a clique and dominating (resp. a clique and 2-dominating). The smallest cardinality of a clique dominating (resp. clique 2-dominating) set in G, denoted by γcl(G) (resp. γ2cl(G)), is called the clique domination number (resp. clique 2-domination number) of G. Any clique dominating (resp. clique 2-dominating) set in G with cardinality γcl(G) (resp. γ2cl(G)) is called a γcl-set (resp. γ2cl-set) in G. We note that not every connected graph admits a clique dominating set (for example, Pn and Cn, where n ≥ 5, do not admit a clique dominating set). A set S ⊆ V (G) is convex if for every two vertices x, y ∈ S, it holds that IG(x, y) ⊆ S. A set S ⊆ V (G) is convex dominating (resp. convex 2-dominating) if S is both convex and dominating (resp. 2-dominating). The minimum cardinality among all convex dominating (convex 2-dominating) sets in G, denoted by γcon(G) (resp. γ2con(G), is called the convex domination number (resp. convex 2-domination number) of G. Any convex dominating (resp. convex 2-dominating) set in G with cardinality γcon(G) (resp. γ2con(G)) is called a γcon-set (resp. γ2con-set) in G. 3. Results Proposition 1. Let G be any connected graph on n vertices. Then max{γcon(G), γ2(G)} ≤ γ2con(G) ≤ n. Moreover, (i) γ2con(G) = 1 if and only if G = K1. (ii) γ2con(G) = 2 if and only if G = K2 or G = K2+H for some graph H of order n−2. Proof. The definition of the convex 2-dominating set implies that max{γcon(G), γ2(G)} ≤ γ2con(G). Since V (G) is convex 2-dominating, the given upper bound follows. (i) Clearly, γ2con(K1) = 1. Suppose γ2con(G) = 1, say S = {v} is a γ2con-set of G. If G ̸= K1, then there exists w ∈ V (G)\S. Since |S| = 1, |NG(w) ∩ S| ≤ 1, a contradiction. Thus, G = K1. (ii) Suppose γ2con(G) = 2 and suppose G ̸= K2. Let S = {x, y} be a γ2con-set in G. Since S is convex, xy ∈ E(G). Let H = ⟨V (G)\S⟩. Since S is a 2-dominating set, z ∈ NG(x) ∩NG(y) for all z ∈ V (H). Hence, G = ⟨S⟩+H ∼= K2 +H. For the converse, suppose that G = K2. Then γ2con(G) = 2. Next, suppose that G = K2 +H for some graph H. Then D = V (K2) is a convex 2-dominating set in G. Hence, γ2con(G) = |D| = 2. Proposition 2. Let G be a connected graph and let S be a convex 2-dominating set in G. Then each of the following holds: R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1542 (i) S(G) ∪ Ind(G) ⊆ S. (ii) If v ∈ V (G) \ S, then ⟨NG(v) ∩ S⟩ is a non-trivial complete graph. Proof. (i) Let p ∈ Ind(G). If p ∈ V (G) \ S, then there exist s, t ∈ S ∩ NG(p) because S is a 2-dominating set. This is not possible since st /∈ E(G) and S is convex. Therefore, p ∈ S, showing that Ind(G) ⊆ S. Next, let w ∈ S(G) and let z ∈ L(G) ∩ NG(w). Since z ∈ S and S is convex, there exists no u ∈ S \ {z} such that uw ∈ E(G). This forces w ∈ S. Since w was arbitrarily chosen, S(G) ⊆ S. (ii) Let v ∈ V (G)\S. Since S is 2-dominating, |NG(v) ∩ S| ≥ 2. Let x, y ∈ NG(v) ∩ S with x ̸= y. Since v ∈ V (G)\S and S is convex, xy ∈ E(G). Thus, ⟨NG(v) ∩ S⟩ is a (non-trivial) complete subgraph of G. Corollary 1. Let G be a connected non-trivial graph. If γ2con(G) = 2, then γ(G) = 1. Observe that since γ(P3) = 1 and γ2con(P3) = 3, the converse of Corollary 1 is not true. Proposition 3. Let G be a connected graph of order n ≥ 2. If γ2con(G) = n, then Ext(G) \ L(G) = ∅. Moreover, if V (G) = S(G) ∪ Ind(G), then γ2con(G) = n. Proof. Suppose that γ2con(G) = n. Suppose there exists v ∈ Ext(G) \ L(G). Then |NG(v)| ≥ 2. Let S = V (G)\{v}. Then S is a convex 2-dominating set in G. Hence, γ2con(G) ≤ |S| = n− 1, a contradiction. Thus, Ext(G) \ L(G) = ∅. The remaining part follows from Proposition 2. Corollary 2. Let G be a connected graph of order n. Then each of the following holds. (i) γ2con(Kn) = { 1, n = 1 2, n ≥ 2. (ii) γ2con(Pn) = n, for all n ≥ 1. (iii) γ2con(Cn) = { 2, n = 3 n, n ≥ 4. (iv) γ2con(K1,n) = n+ 1, for all n ≥ 1. Proposition 4. Let G = Kn1,n2,...,nk be the complete k-partite graph with 2 ≤ n1 ≤ n2 ≤ · · · ≤ nk, where k ≥ 2. Then γ2con(G) = { n1 + n2 if k = 2 3 if k ≥ 3. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1543 Proof. Let Sn1 , Sn2 , . . . , Snk be the partite sets in G. Suppose first that k = 2. Suppose further that D ̸= V (G), say v ∈ V (G) \ D. We may assume that v ∈ Sn1 . Since D is 2-dominating, there exist a, b ∈ Sn2 ∩NG(v). This, however, implies that D is not convex, a contradiction. Thus, D = V (G), showing that γ2con(G) = n1 + n2. Next, suppose that k ≥ 3. Since G is non-trivial and G ̸= K2 +H for any graph H, γ2con(G) ≥ 3 by Proposition 1. Pick any vi ∈ Sni for i = 1, 2, 3 and let S = {v1, v2, v3}. Then ⟨S⟩ is complete. Hence, S is a convex set in G. Clearly, S is also a 2-dominating set. Therefore, γ2con(G) = |S| = 3. Theorem 1. [15] For a cycle Cn on n ≥ 6 vertices, γcon(Cn) = n. Theorem 2. Let a and b be positive integers such that 6 ≤ a ≤ b. Then there exists a connected graph G such that γcon(G) = a and γ2con(G) = b. Proof. Consider the following cases: Case 1: a = b. Let G = Ca. Then γcon(G) = a = γ2con(G), by Theorem 1 and Corollary 2(iii). Case 2: a < b. Let m = b − a. Consider the graph G in Figure 1. Let S be a γcon-set in G. Since S is a convex dominating set, va ∈ S. By Observation 1, {v1, v2, . . . , va−1} ⊆ S. Since S is a γcon-set in G, S = {v1, v2, . . . , va}. Hence, γcon(G) = |S| = a. Next, let D be a γ2con-set in G. Since Ind(G) = V (G), γ2con(G) = |D| = |V (G)| = a+m = b by Proposition 3. v1 v2 · · · v3 va−2 va−1 va x1 x2 · · · xm−1 xm Figure 1: A graph G with γcon(G) = a and γ2con(G) = b This proves the assertion. The join of two graphs G and H, denoted by G + H, is the graph with V (G+H) = V (G)∪V (H) and E(G+H) = E(G)∪E(H)∪{uv : u ∈ V (G) and v ∈ V (G)}, where “∪” refers to a disjoint union of sets. Theorem 3. Let G and H be non-complete graphs. Then S ⊆ V (G + H) is a convex 2-dominating set in G+H if and only if one of the following holds: R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1544 (i) S = V (G+H). (ii) S is a clique 2-dominating set in G. (iii) S is a clique 2-dominating set in H. (iv) S = SG ∪ SH where ∅ ̸= SG ⊆ V (G) and ∅ ̸= SH ⊆ V (H) satisfy any of the following: (a) SG and SH are cliques in G and H, respectively, where |SG| ≥ 2 and |SH | ≥ 2. (b) SG and SH are dominating sets in G and H, respectively, with |SG| = |SH | = 1. (c) |SG| = 1 and SH is a clique dominating set in H with |SH | ≥ 2. (d) |SH | = 1 and SG is a clique dominating set in G with |SG| ≥ 2. Proof. Suppose S is a convex 2-dominating set in G+H where S ̸= V (G+H). Suppose first that S ⊆ V (G). Since S is a convex 2-dominating set in G+H, S must be a clique 2-dominating set in G. Similarly, if S ⊆ V (H), S is a clique 2-dominating set in H. Hence, (ii) or (iii) holds. Next, suppose that SG = S ∩ V (G) ̸= ∅ and SH = S ∩ V (H) ̸= ∅. Since S is convex and G and H are non-complete, SG and SH are cliques in G and H, respectively. If |SG| ≥ 2 and |SH | ≥ 2, then (a) holds. Suppose |SG| = 1 and |SH | = 1. Since S is 2-dominating in G + H, it follows that SG and SH are dominating sets in G and H, respectively, showing that (b) holds. Suppose |SG| = 1 and |SH | ≥ 2. Since SH ̸= V (H) (otherwise S = V (G+H)) and S is convex 2-dominating in G+H, SH is a clique dominating set in H. Hence, (c) holds. Similarly, (d) holds if |SG| ≥ 2 and |SH | = 1. The converse is clear. Corollary 3. Let G and H be non-complete graphs such that γ(G) = γ(H) = 1. Then γ2con(G+H) = 2. Lemma 1. Let G be a non-trivial connected graph. If G admits a clique 2-dominating set, then 1 + γcl(G) ≤ γ2cl(G). Proof. LetD be a γ2cl-set inG. Then, clearly, |D| ≥ 2. Let v ∈ D and setD∗ = D\{v}. If |D| = 2, then |D∗| = 1 and D∗ is a dominating set in G. Suppose |D| ≥ 3 Let z ∈ V (G) \ D∗. If z ∈ D, then zw ∈ E(G) for every w ∈ D∗. Suppose z ∈ V (G) \ D. Since D is 2-dominating, |NG(z)∩D| ≥ 2. It follows that |NG(z)∩D∗| ≥ 1, showing that D∗ is a clique dominating set in G. Thus, γcl(G) ≤ |D∗| = γ2cl(G) − 1. This proves the assertion. The next result follows from Theorem 3 and Lemma 1. Corollary 4. Let G and H be non-complete graphs such that γ(G) ̸= 1 and γ(H) ̸= 1. (i) If G and H both admit a clique 2-dominating set (a clique dominating set), then γ2con(G+H) = min{1 + γcl(G), 1 + γcl(H), 4}. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1545 (ii) If G admits a clique dominating set but H does not, then γ2con(G+H) = min{1 + γcl(G), 4}. (iii) If G and H are disconnected graphs, then γ2con(G+H) = { 4 if E(G) ̸= ∅ and E(H) ̸= ∅ |V (G+H)| if E(G) = ∅ or E(H) = ∅. Theorem 4. Let G be a non-complete graph and let n be a positive integer. A subset S ⊆ V (Kn + G) is convex 2-dominating in Kn + G if and only if one of the following holds: (i) S ⊆ V (Kn) and |S| ≥ 2. (ii) S is a clique 2-dominating set in G. (iii) S = SG ∪ Sn where ∅ ̸= SG ⊆ V (G) and ∅ ̸= Sn ⊆ V (Kn) satisfies any of the following: (a) Sn = V (Kn) and V (G) \ SG is a non-connecting set in G, where, in addition, SG is dominating if n = 1. (b) Sn ̸= V (Kn) with |Sn| = 1 and SG is a clique dominating set in G. (c) Sn ̸= V (Kn) with |Sn| ≥ 2 and SG is a clique in G. Proof. Suppose S is a convex 2-dominating set in Kn + G. If S ⊆ V (Kn), then |S| ≥ 2, showing that (i) holds. Suppose that S ⊆ V (G). Since G is non-complete and S is convex and 2-dominating in G + H, S is a clique dominating set in G. Hence, (ii) holds. Next, suppose SG = V (G) ∩ S ̸= ∅ and Sn = V (Kn) ∩ S ̸= ∅. Suppose first that Sn = V (Kn). Let p, q ∈ SG such that dG(p, q) = 2. Since S is convex in Kn + G, IG(p, q) = IKn+G(p, q) \ V (Kn) ⊆ IKn+G(p, q) ⊆ S. It follows that IG(p, q) ⊆ SG. Hence, NG(p) ∩ NG(q) ∩ (V (G) \ SG) = ∅. This shows that V (G) \ SG is a non-connecting set in G. If n = 1, then SG is a dominating set because S is a 2-dominating set in Kn + G. Thus, (a) holds. Now suppose that Sn ̸= V (Kn). Since S is convex, SG is a clique in G. Moreover, since S is 2-dominating in Kn + G, SG is a dominating set in G if |Sn| = 1. This shows that (b) or (c) holds. The converse is easy. The next result is immediate from Theorem 4. Corollary 5. Let G be a non-complete graph and let n be a positive integer. Then γ2con(Kn +G) = { 1 + ψG if n = 1 2 if n ≥ 2 where ψG = min{|S| : S is a dominating set and V (G) \S is a non-connecting set in G}. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1546 Let G and H be connected graphs. The corona of G and H is the graph G◦H obtained by taking one copy of G and |V (G)| copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H. For convenience, we write Hv to denote the copy of H joined to v and write Hv + v = Hv + ⟨v⟩. Remark 1. Let G be a non-trivial connected graph. If S is a clique in G, then V (G) \ S is a non-connecting set. Theorem 5. Let G be a non-trivial connected graph and let H be any graph. Then S is a convex 2-dominating set in G ◦H if and only if S = V (G) ∪ (⋃ v∈V (G) Sv ) where Sv is dominating and V (Hv) \ Sv is a non-connecting set in Hv for each v ∈ V (G). Proof. Let S be a convex 2-dominating set in G ◦ H. Let A = S ∩ V (G) and let Sv = S ∩ V (Hv) for each v ∈ V (G). Then S = A ∪ (⋃ v∈V (G) Sv ) . Suppose A ̸= V (G). Then there exists u ∈ V (G) \ A. Since S is a dominating set, Su ̸= ∅. Since G is a non-trivial connected graph, ⟨S⟩ is disconnected, a contradiction to the assumption that S is convex. Hence, A = V (G) and S = V (G)∪ (⋃ v∈V (G) Sv ) . Next, let v ∈ V (G). Since v ∈ S and S ∩ [V (Hv) ∪ {v}] is a convex 2-dominating set in v +Hv, Sv is a dominating set, and V (Hv) \ Sv is a non-connecting set in Hv by Theorem 4(iii)(a). Conversely, suppose that S has the given form and satisfies the given property. Then S is a 2-dominating set in v+Hv. By Theorem 4(iii)(a), Sv∪{v} is a convex 2-dominating set in v+Hv for each v ∈ V (G). Since G is connected, it follows that ⋃ v∈V (G) (Sv ∪ {v}) = S is a convex set in G ◦H. Hence, S is a convex 2-dominating set in G ◦H. Corollary 6. Let G be a nontrivial connected graph of order m and let H be any graph. Then γ2con(G ◦H) = m(1 + ψH), where ψH = min{|S| : S is a dominating set and V (H)\S is a non-connecting set in H}. Proof. Let S = V (G) ∪ (⋃ v∈V (G) Sv ) be a γ2con-set in G ◦H. By Theorem 5, Sv is a dominating set, and V (Hv) \ Sv is a non-connecting set in Hv. Thus γ2con(G ◦H) = |S| = |V (G)|+ ∑ v∈V (G) |Sv| ≥ m(1 + ψH). Next, let Dv be a dominating set in Hv such that V (Hv) \Dv is non-connecting and |Dv| = ψH for each v ∈ V (G). Then S∗ = V (G)∪ (⋃ v∈V (G)Dv ) is a convex 2-dominating set in G ◦H by Theorem 5. Hence, γ2con(G ◦H) ≤ |S∗| R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1547 = |V (G)|+ ∑ v∈V (G) |Dv| = m(1 + ψH). This proves the desired equality. The Cartesian product G × H of two graphs G and H is the graph with V (G×H) = V (G)× V (H) and (u, u′)(v, v′) ∈ E(G×H) if and only if either uv ∈ E(G) and u′ = v′ or u = v and u′v′ ∈ E(H). The next result obtained by Canoy and Garces characterizes convex sets in the Carte- sian product of graphs. Theorem 6. [7] Let G and H be connected graphs. A subset S of V (G□H) is convex if and only if S = S1 × S2, where S1 and S2 are convex sets in G and H, respectively. Lemma 2. Let G and H be connected graphs. If a subset S = S1 × S2 of V (G□H) is a 2-dominating set in G□H, then S1 and S2 are 2-dominating sets in G and H, respectively. Proof. Suppose that S is a 2-dominating set in G□H and let v ∈ V (G) \ S1. Pick any p ∈ V (H). Since S is 2-dominating in G□H and (v, p) /∈ S, there exist (u, q), (w, t) ∈ S∩NG□H((v, p)). This implies that p = q = t, u ̸= w, and u,w ∈ S1∩NG(v). Thus, S1 is a 2-dominating set in G. A similar argument can be used to show that S2 is a 2-dominating set in H. Theorem 7. Let G and H be connected graphs. A subset S of V (G□H) is a convex 2-dominating set in G□H if and only if S = S1 × S2 and (i) S1 is a convex 2-dominating set in G and S2 = V (H), or (ii) S2 is a convex 2-dominating set in H and S1 = V (G). Proof. Let S be a convex 2-dominating set in G□H. By Theorem 6, S = S1 × S2, where S1 and S2 are convex sets in G and H, respectively. By Lemma 2, S1 and S2 are 2-dominating sets in G and H, respectively. Suppose S1 ̸= V (G) and S2 ̸= V (H). Pick any x ∈ V (G) \ S1 and a ∈ V (H) \ S2. Then (x, d), (z, a) /∈ S for all d ∈ V (H) and z ∈ V (G). It follows that NG□H((x, a)) ∩ (S1 × S2) = ∅, implying that S1 × S2 is a not a 2-dominating set in G□H, contrary to our assumption of the set. Hence, S1 = V (G) or S2 = V (H). This shows that (i) or (ii) holds. For the converse, suppose that (i) holds. By Theorem 6, S = S1 × S2 is a convex set in G□H. Let (v, p) ∈ V (G□H) \ S. Then v /∈ S1. Since S1 is 2-dominating, there exist u,w ∈ S1 such that u,w ∈ NG(v). Consequently, (u, p), (w, p) ∈ NG□H((v, p))∩S. Hence, S is a convex 2-dominating set in G□H. The same conclusion is obtained if (ii) holds. Corollary 7. Let G and H be connected graphs of orders m and n, respectively. Then γ2con(G□H) = min{mγ2con(H), nγ2con(G)}. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1548 Proof. Let S be a γ2con-set in G□H. By Theorem 7, S = S1×V (H) or S = V (G)×S2, where S1 is a convex 2-dominating set in G and S2 is a convex 2-dominating set in H. Thus, γ2con(G□H) = |S| ≥ min{nγ2con(G),mγ2con(H)}. Next, suppose that S′ 1 and S ′ 2 are γ2con-sets inG andH, respectively. Then by Theorem 7, S′ = S′ 1 × V (H) and S∗ = V (G)× S′ 2 are convex 2-dominating sets in G□H. It follows that γ2con(G□H) ≤ min{|S′|, |S∗|} = min{nγ2con(G),mγ2con(H)}. This proves the desired equality. The lexicographic product of two graphs G and H is the graph G[H] with V (G[H]) = V (G)×V (H) and (u1, u2)(v1, v2) ∈ E(G[H]) if and only if either u1v1 ∈ E(G) or u1 = v1 and u2v2 ∈ E(H). Theorem 8. [7] Let G and H be connected non-complete graphs and let C be a proper subset of V (G[H]). Then C is convex in G[H] if and only if C is a clique. Theorem 9. Let G and H be connected non-complete graphs. A set C = ∪x∈S({x}×Tx) ⊆ V (G[H]) is convex 2-dominating if and only if C = V (G[H]) or S and each Tx are cliques in G and H, respectively, and satisfy one of the following conditions: (i) S is a 2-dominating set in G and (a) |S| ≥ 3 or (b) for each x ∈ S, Tx is dominating in H or |Ty| ≥ 2 when S = {x, y}. (ii) S is a dominating set in G such that (c) Tx is 2-dominating in H whenever S = {x} and (d) for each v ∈ V (G) \ S with |NG(v) ∩ S| = 1, it holds that |Tz| ≥ 2 for z ∈ NG(v) ∩ S. Proof. Suppose C is convex 2-dominating and C ̸= V (G[H]). By Theorem 8, S and Tx are cliques in G and H, respectively, for each x ∈ S. Suppose S is 2-dominating in G and let x ∈ S. If |S| ≥ 3, then (i)(a) holds. Suppose |S| = 2, say S = {x, y} and suppose that |Ty| = 1. Let p ∈ V (H) \ Tx and q ∈ Ty. Then (y, q) ∈ C ∩ NG[H]((x, p)). Since C is 2-dominating in G[H], there exists (z, t) ∈ (C \ {(y, q)}) ∩NG[H]((x, p)). Since Ty = {q}, z = x and t ∈ Tx ∩ NH(p). Therefore, Tx is a (clique) dominating set in H, showing that (i)(b) holds. Next, suppose that S is not 2-dominating. Since C is dominating, it follows that S is a (clique) dominating set in G. Suppose first that |S| = 1, say S = {x}. Let d ∈ V (H) \ Tx. Since C is 2-dominating and (x, d) /∈ C, there exist (v, l), (w, s) ∈ C∩NG[H]((x, d)). This implies that v = w = x and l, s ∈ Tx∩NH(d). Thus, Tx is a (clique) 2-dominating set in H. Finally, let v ∈ V (G) \ S with |NG(v) ∩ S| = 1, say NG(v) ∩ S = {z}. Since C is 2-dominating, |Tz| ≥ 2, showing that (ii) holds. The converse is easy. R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1549 Corollary 8. Let G and H be connected two non-complete graphs of orders m and n, respectively. If G and H do not admit a clique dominating set, then γ2con(G[H]) = mn. Corollary 9. Let G and H be connected non-complete graphs. Then γ2con(G[H]) = 2 if and only if γcl(G) = 1 and γ2cl(H) = 2 or γcl(H) = 1 and γ2cl(G) = 2. Proof. Suppose γ2con(G[H]) = 2 and let C = {(x, a), (y, b)} be a γ2con-set in G[H]. Then (x, a), (y, b) ∈ E(G[H]) because C is convex. If x = y, then ab ∈ E(H). Hence, γcl(G) = 1 (x is a dominating vertex of G) and so γ2cl(H) = 2 by Theorem 9(ii)(c). Suppose x ̸= y. Then {x, y} is a 2-dominating set in G, i.e., γ2cl(G) = 2. Since |Tx| = |Ty| = 1, Tx and Ty are clique dominating sets in H by Theorem 9(i)(b). Thus, γcl(H) = 1. The converse follows from Theorem 9. Corollary 10. Let G and H be connected non-complete graphs. Then γ2con(G[H]) = 3 if and only if one of the following holds: (i) γ2cl(G) = 3. (ii) γcl(G) = 1 and γ2cl(H) = 3. (iii) γ2cl(G) = 2 and γcl(H) = 2. (iv) γcl(G) = γcl(H) = 1, γ2cl(G) ̸= 2, and γ2cl(H) ̸= 2. (v) γcl(H) = 2, γcl(G) = 1, and γ2cl(H) ̸= 2. Proof. Suppose γ2con(G[H]) = 3 and let C = {(w, p), (u, q), (v, r)} be a γ2con-set in G[H]. Then C is a clique by Theorem 8. If u, v, and w are distinct vertices of G, then γ2cl(G) = 3, showing that (i) holds. If w = u = v, then {p, q, r} is a clique in H. Hence, γcl(G) = 1 (w is a dominating vertex of G) and γ2cl(H) = 3 by Theorem 9(ii). This shows that (ii) holds. Suppose now that w = u and v ̸= w. Then Q = {v, w} is a clique dominating set in G. If Q is 2-dominating, then γ2cl(G) = 2. Since γ2con(G[H]) ̸= 2, γcl(H) ̸= 1. It follows that {p, q} is a γcl-set in H, i.e., γcl(H) = 2. Hence, (iii) holds. Suppose Q is not 2-dominating. Let z ∈ V (G) \ Q such that z /∈ NG(w) ∩ NG(v). Since C is 2-dominating, this implies that z ∈ NG(w). It follows that w is a dominating vertex of G. Thus, γcl(G) = 1. By Corollary 9, γ2cl(H) ̸= 2. Suppose γcl(H) = 1 (p or q is a dominating vertex of H). Since γ2con(G[H]) ̸= 2, γ2cl(G) ̸= 2. Therefore, (iv) holds. If γcl(H) ̸= 1, then γcl(H) = 2, showing that (v) holds. For the converse, suppose first that (i) holds. Let S = {x, y, z} be a γ2cl-set in G and pick any p ∈ V (H). Then C1 = {(x, a), (y, a), (z, a)} is a γ2con-set of G[H] by Theorem 9 and Corollary 9. Suppose (ii) holds, say D = {p, q, t} is a γ2cl-set in H. Let v be a dominating vertex in G. Then C2 = {(v, p), (v, q), (v, t)} is a γ2con-set of G[H] by Theorem 9 and Corollary 9. Next, suppose (iii) holds. Let {x, y} be a γ2cl-set in G and let {k, l} be γcl-set in H. Then C3 = {(x, k), (x, l), (y, k)} is a γ2con-set of G[H] by Theorem 9 and Corollary 9. Suppose now that (iv) holds. Let w and p be dominating vertices of G and R. J. G. Fortosa et al. / Eur. J. Pure Appl. Math, 17 (3) (2024), 1539-1552 1550 H, respectively. Let u ∈ NG(w) and s ∈ NH(p). Let C4 = {(w, p), (w, s), (u, p)}. By Theorem 9 and Corollary 9, C3 is a γ2con-set of G[H]. Lastly, suppose that (v) holds. Let w be a dominating vertex of G, v ∈ NG(w), and let R = {a, b} be a γcl-set in H. Then C5 = {(w, a), (w, b), (v, a)} is a γ2con-set of G[H] by Theorem 9 and Corollary 9. Accordingly, γ2con(G[H]) = 3. Corollary 11. Let G and H be connected non-complete graphs such that γcl(G) ≥ 2. Suppose H does not admit a clique dominating set. (i) If G admits a clique 2-dominating set, then γ2con(G[H]) ≤ min{2γcl(G), γ2cl(G)}. (ii) If G does not admit a clique 2-dominating set, then γ2con(G[H]) ≤ 2γcl(G). The bound given in Corollary 11 is sharp. Indeed, γ2con(P4[Pn]) = 4 = 2γcl(P4) and γ2con(C4[Cn]) = 4 = 2γcl(C4) for all n ≥ 5. The next result is a rectification of the one obtained by Canoy and Garces in [7]. Theorem 10. [6] Let G be a connected graph and m a positive integer. A set C = ∪v∈S({x}×Tx) ⊆ V (G[Km]), where S ⊆ V (G) and Tx ⊆ V (Km) for all x ∈ S, is con- vex in G[Km] if and only if S is convex in G and Tx = V (Km) for each x ∈ S0 = I(S)∩S. Theorem 11. Let G be a non-trivial connected graph and m a positive integer. A set C = ∪v∈S({x}×Tx) ⊆ V (G[H]), where S ⊆ V (G) and Tx ⊆ V (Km) for all x ∈ S, is convex 2-dominating in G[Km] if and only if S is convex 2-dominating in G and Tx = V (Km) for each x ∈ S0 = I(S) ∩ S. Proof. Suppose C is convex 2-dominating in G[Km]. By Theorem 10, S is convex in G and Tx = V (Km) for each x ∈ S0 = I(S) ∩ S. Let v ∈ V (G) \ S and choose any p ∈ V (Km). Since (v, p) /∈ C and C is 2-dominating in G[Km], there exist two vertices (w, t), (z, s) ∈ C ∩ NG[Km]((v, p)). This implies that w, z ∈ S ∩ NG(v). Therefore, S is a 2-dominating set in G. Conversely, suppose that S is convex in G and Tx = V (Km) for each x ∈ S0 = I(S)∩S. Then C is convex in G[Km] by Theorem 10. Let (y, d) ∈ V (G[Km])\C. Suppose y ∈ S. Since S is convex 2-dominating, it follows that |S| ≥ 2 and ⟨S⟩ is con- nected. Let u ∈ S ∩ NG(y). Pick any a ∈ Ty and b ∈ Tu. Then (y, a), (u, b) ∈ C ∩ NG[Km]((y, d)). Next, suppose that y /∈ S. Since S is 2-dominating in G, there exist distinct vertices v, w ∈ S ∩NG(y). Choose any p ∈ Tv and q ∈ Tw. Then (v, p), (w, q) ∈ C ∩NG[Km]((y, d)). Thus, C is a 2-dominating set in G[Km]. Corollary 12. Let G be a non-trivial connected graph and let m ≥ 2. Then γ2con(G[Km]) = min{|S|+ (m− 1)|S0| : S is a convex 2-dominating set in G}. REFERENCES 1551 Conclusion Convex 2-domination has been introduced and initially studied in this paper. It was shown that every support vertex and every vertex with an independent open neighborhood belong to every convex 2-dominating set in a connected graph. The convex 2-domination number of a connected graph is at least equal to its convex domination number. Moreover, the difference of these two parameters can be made arbitrarily large. Convex 2-domination has been investigated for the join and corona of two graphs as well as for the lexicographic and Cartesian products of graphs. For some graphs (especially for some join and lexi- cographic product of graphs), convex 2-domination is related to clique domination. The newly defined concept can be studied for other graphs. It is also interesting to determine the complexity of the convex 2-domination problem. References [1] S. Banerjee, J.M. Keil, and D. Pradhan. Perfect Roman domination in graphs. The- oretical Computer Science, 796:1–21, 2019. [2] R.A. Beeler, T.W. Haynes, and S.T. Hedetnieme. Double Roman domination. Dis- crete Applied Mathematics, 211:23–29, 2016. [3] B. Brešar and S. Brezovnik. Grundy domination and zero forcing in regular graphs. Bulletin of the Malaysian Mathematical Sciences Society, 44(6):3637–3661, 2021. [4] G. Cagaanan and S. Canoy Jr. On the geodetic covers and geodetic bases of the composition g [km]. Ars Combinatoria, 79:33–45, 2006. [5] G. Cagaanan and S. Canoy Jr. Bounds for the geodetic number of the cartesian product of graphs. Utilitas Mathematica, 79:91–98, 2009. [6] S.R. Canoy. A short note on convexity and convex domination in G[Km]. Applied Mathematical Sciences, 8(115):5737–5741, 2014. [7] S.R. Canoy and I.J.L. Garces. Convex sets under some graph operations. Graphs and Combinatorics, 18(4):787–793, 2002. [8] G. Chartrand, J.F. Fink, and P. Zhang. Convexity in oriented graphs. Discrete applied mathematics, 116(1-2):115–126, 2002. [9] G. Chartrand and P. Zhang. Convexity in graphs. Congr. Numerantium, 136:19–32, 1999. [10] M. Chellali. Bounds on the 2-domination number in cactus graphs. Opuscula Math- ematica, 26(1):5–12, 2006. [11] M. Chellali, T.W. Haynes, and S.T. Hedetnieme. Roman {2}- domination. Discrete Applied Math, 204:22–28, 2016. REFERENCES 1552 [12] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae. Roman 2-domination. Discrete Applied Mathematics, 204:22–28, 2016. [13] E.J. Cockayne, R.M. Dawes, and S.T. Hedetniemi. Total domination in graphs. Net- works, 10(3):211–219, 1980. [14] E.J. Cockayne, P.A. Deryer, S.M. Hedetnieme, and S.T. Hedetnieme. Roman Domi- nation in Graphs. Discrete Mathematics, 278(13):11–22, 2004. [15] J. Cyman, M. Lemańska, and J. Raczek. Graphs with convex domination number close to their order. Discussiones Mathematicae Graph Theory, 26(2):307–316, 2006. [16] M. Dettlaff and M. Lemańskaand J.A. Rodŕıguez-Velázquez. Secure italian domina- tion in graphs. Journal of Combinatorial Optimization, 41:56–72, 2021. [17] M. Farber and R.E. Jamison. Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3):433–444, 1986. [18] R.J. Fortosa and S.R. Canoy. Convex roman dominating function in graphs. European Journal of Pure and Applied Mathematics, 16(3):1705–1716, 2023. [19] R.J. Fortosa, S.R. Canoy, and F.P. Jamil. Convex italian in graphs. Kyungpook Mathematical Journal, submitted. [20] W. Goddard and M.A. Henning. Domination in planar graphs with small diameter. Journal of Graph Theory, 40(1):1–25, 2002. [21] G. Hao, P. Jalilolghadr, and D.A. Mojdeh. Perfect double italian domination of a graph. AKCE International Journal of Graphs and Combinatorics, 20(3):247–257, 2023. [22] F. Harary and J. Nieminen. Convexity in graphs. Journal of Differential Geometry, 16(2):185–190, 1981. [23] T.W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of domination in graphs. CRC press, 2013. [24] M. Lemanska. Weakly convex and convex domination numbers. Opuscula Mathemat- ica, 24(2):181–188, 2004. [25] B. Omamalin, S.R. Canoy Jr., and H. Rara. Locating total dominating sets in the join, corona and composition of graphs. Applied Mathematical Sciences, 8(48):2363–2374, 2014. [26] L.M. Paleta and F.P. Jamil. On perfect italian domination in graphs. Discrete Mathematics, Algorithms and Applications, page 2350085, 2023. [27] C.S. Revelle and K.E. Rosing. Defendens imperium romanum: a classical problem in military strategy. American Mathematical Monthly, 107(7):585–594, 2000. [28] I. Stewart. Defend the Roman empire! Scientific American, 281(6):136–138, 1999.