EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 4, Article Number 6939 ISSN 1307-5543 – ejpam.com Published by New York Business Global Connected Disjunctive Domination in Graphs Alkajim Ahadi Aradais1,3,∗, Ferdinand P. Jamil2,3, Sergio R. Canoy, Jr.2,3 1 Department of Mathematics, College of Arts and Sciences, MSU-Tawi-Tawi College of Technology and Oceanography, 7500 Bongao, Tawi-Tawi, 2 Department of Mathematics and Statistics, College of Science and Mathematics 3 Center for Mathematical and Theoretical Physical Sciences, Premier Research Institute of Science and Mathematics, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. A set S of vertices of a graph G is a disjunctive dominating set if for every v ∈ V (G)\S, v is adjacent to a vertex in S or S contains two vertices each of distance two from v. A disjunctive dominating set S is a connected disjunctive dominating set if ⟨S⟩ is connected. In this paper, we study the concept of connected disjunctive dominating set. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Connected disjunctive dominating set, connected disjunctive domi- nation number, join, corona, lexicographic product 1. Introduction In 2014, Goddard et al.[1] introduced the concept of disjunctive, specifically b-disjunctive, domination in graphs. While most of the variations on dominating sets tend to increase the domination number, which in effect raise implementation costs, disjunctive domina- tion is a relaxation of the domination number [2]. In [1], sharp bounds for the disjunctive domination number were established for general graphs, and exact values were determined for specific graphs. In 2016, Henning and Naicker [2] introduced the disjunctive total domination. Accord- ingly, it allows for greater flexibility by modeling networks where one trades off redundancy and backup capability with resource optimization. The above-mentioned authors estab- lished in [2] tight upper bound on the disjunctive total domination number of a graph in terms of its order and characterized the extremal graphs, and then proved that this bound can be significantly improved if claw-freeness of a graph is imposed. The same authors also investigated the variant on the class of trees in [3]. In [4, 5], Malalay and Jamil explored ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i4.6939 Email addresses: alkajimaradais@msutawi-tawi.edu.ph (A. Aradais) ferdinand.jamil@g.msuiit.edu.ph (F. Jamil) sergio.canoy@g.msuiit.edu.ph (S. Canoy) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 2 of 14 both the disjunctive domination and disjunctive total domination, and initiated the study of restrained disjunctive domination in graphs under some binary operations. In this present paper, we introduce and initiate the study of connected disjunctive domination. First, we investigate the concept for some special graphs, and characterize the graphs which give small values for the corresponding parameter. Then we study connected disjunctive domination for families of graphs involving some binary operations. 2. Terminology and Notations Throughout this paper, we only consider graphs which are finite, simple and undirected. All basic terminologies which are not defined but are being used here are adapted from [6]. For a graph G, the symbols V (G) and E(G) refer to the vertex-set and edge-set, respectively, of G. For S ⊆ V (G), |S| is the cardinality of S. In particular, |V (G)| is called the order of G. A graph G is connected if for every pair of distinct vertices u and v of G, G contains a path from u to v. If G is connected and u, v ∈ V (G), then dG(u, v), the distance from u to v, is the length of the shortest path connecting u and v. A vertex u is a cut-vertex if the removal of u from G increases the number of components of G. Given graphs G and H, the join of G and H is the graph G + H with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)}. 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 in the ith copy of H. In particular, we call G ◦K1 the corona of G, and write cor(G) = G ◦K1. The composition (or lexicographic product) of G and H is the graph G[H] with V (G[H]) = V (G) × V (H) and (u, v)(u′, v′) ∈ E(G[H]) if and only if either uu′ ∈ E(G) or u = u′ and vv′ ∈ E(H). In any of these graphs, G and H are referred to as their basic component graphs. Vertices u and v of a graph G are neighbors if uv ∈ E(G). The open neighborhood of v refers to the set NG(v) consisting of all neighbors of v. The degree of v, denoted degG(v), refers to the cardinality |NG(v)| of the open neighborhood of v. Vertex v is an end-vertex if degG(v) = 1. The closed neighborhood of v is the set NG[v] = NG(v)∪{v}. Customarily, for S ⊆ V (G), NG(S) = ∪v∈SNG(v) and NG[S] = ∪v∈SNG[v]. A subset S ⊆ V (G) is a dominating set of G if NG[S] = V (G). If NG(S) = V (G), then S is a total dominating set of G. The minimum cardinality of a dominating set of G is the domination number of G, and the minimum cardinality of a total dominating set is the total domination number of G. We write γ(G) and γt(G) to denote the domination number and total domination number, respectively, of G. A dominating set of cardinality γ(G) is called a γ-set of G. Similarly, a γt-set is a total dominating set of cardinality γt(G). The reader is referred to [7–10] for the history, fundamental concepts and recent developments of domination in graphs as well as its various applications, and to [11–13] for studies whose primary emphasis is on total domination in graphs. A dominating set S is a connected dominating set of G provided the subgraph ⟨S⟩ induced by S is connected. The minimum cardinality of a connected dominating set, A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 3 of 14 which is denoted by γc(G), is the connected domination number of G. The problem of connected domination would arise in real life in the following scenario. An existing computer network with direct connections described by a graph G must have the property that any computer turned on must always be able to send a message to any other computer turned on. One can make sure a computer is always on by connecting it to an (expensive) unlimited power supply (UPS) source. The requirement is met by connecting only the computers in a connected dominating set to such power sources. A set S ⊆ V (G) is a 2-dominating set of G if for each v ∈ V (G) \ S, |NG(v) ∩ S| ≥ 2. It is a connected 2-dominating set of G if it is a 2-dominating set and ⟨S⟩ is connected. The minimum cardinality of a 2-dominating set (resp. connected 2-dominating set) is the 2-domination number (resp. connected 2-domination number) of G, denoted by γ×2(G) (resp. γ×2,c(G)). Any 2-dominating (resp. connected 2-dominating) set with cardinality γ×2(G) (resp. γ×2,c(G)) is called a γ×2-set (resp. γ×2,c-set) of G. Excellent references for studies of 2-domination include [14–19]. For a vertex v of G, NG(v, 2) = {u ∈ V (G) \ {v} : dG(u, v) ≤ 2}. For S ⊆ V (G), NG(S, 2) = ∪v∈SNG(v, 2). A set S ⊆ V (G) is a distance-two dominating set of G pro- vided V (G) \ S ⊆ NG(S, 2), i.e., if for every v ∈ V (G) \ S there exists u ∈ S such that dG(u, v) ≤ 2. A distance-two dominating set S is a connected distance-two dominating set if ⟨S⟩ is connected. The minimum cardinality of a distance-two dominating set (resp. connected distance-two dominating set) is the distance-two domination number (respec- tively connected distance-two domination number) of G. We use the symbols γ2(G) and γ2,c(G) for the distance-two domination number and connected distance-two domination number, respectively, of G. A distance-two dominating set (resp. connected distance-two dominating set) of cardinality γ2(G) (resp. γ2,c(G)) is called a γ2-set (resp. γ2,c-set) . The articles in [20, 21] are good references for studies in distance-two domination. In [21] the connected distance-two domination is called connected 2-distance domination. A subset S ⊆ V (G) is a connected distance-two dominating set of G if S is a distance- two dominating set of G for which ⟨S⟩ is connected. In [21], the same is called connected 2-distance dominating set. We used γ2,c(G) to denote the minimum cardinality of a con- nected distance-two dominating set of G. A set S ⊆ V (G) is a disjunctive dominating set of G if for every v ∈ V (G) \ S, v is a neighbor of a vertex in S or S has at least two vertices each at distance 2 from v. Provided G has no isolated vertex, S ⊆ V (G) is a disjunctive total dominating set if for every v ∈ V (G), v is adjacent to a vertex of S or S has at least two vertices each at distance 2 from v. The minimum cardinality of a disjunctive dominating set (resp. disjunctive total dominating set) is the disjunctive domination number (resp. disjunctive total domination number) of G. We write γd(G) and γdt (G) to denote the disjunctive domination number and disjunctive total domination number, respectively, of G. A disjunctive dominating set of cardinality γd(G) is called a γd-set. Any disjunctive total dominating set of cardinality γdt (G) is called γdt -set. For convenience, the symbol Nd G(S) denotes the set of all x ∈ V (G) such that xy ∈ A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 4 of 14 E(G) for some y ∈ S or there exist distinct u, v ∈ S with dG(x, u) = 2 = dG(x, v). Precisely, S is a disjunctive dominating set (resp. disjunctive total dominating set) of G if and only if V (G) \ S ⊆ Nd G(S) (resp. V (G) = Nd G(S). Since NG(S) ⊆ Nd G(S), dominating sets are disjunctive dominating sets. In particular, γd(G) = 1 if and only if γ(G) = 1; and if γ(G) = 2, then γd(G) = 2, but not conversely. Note, for example, that for path P3 on 3 vertices and any graph G, γd(P3◦G) = 2 while γ(P3◦G) = 3. Also, since total dominating sets are disjunctive total dominating sets, γdt (G) ≤ γt(G) for all graphs G without isolated vertices. In particular, if γt(G) = 2, then γdt (G) = 2. The converse, however, need not be true. Note that for cycle C5, γt(C5) = 3 but γdt (C5) = 2. 3. Results A disjunctive dominating set S is a connected disjunctive dominating set provided ⟨S⟩ is connected. The minimum cardinality of a connected disjunctive dominating set of G, denoted by γdc (G), is the connected disjunctive domination number of G. Any connected disjunctive dominating set of cardinality γdc (G) is called a γdc -set of G. We denote by Pn, Cn, Kn and Kn the path, cycle, complete graph and empty graph on n vertices. For positive integers n1, n2, . . ., nk, we denote by Kn1,n2,...,nk the complete multipartite graph with partite sets Un1 , Un2 , . . ., Unk with |Unj | = nj for each j ∈ {1, 2, . . . , k}. In particular, a star on n+ 1 vertices is denoted by K1,n. A subdivision of an edge uv ∈ E(G) is obtained by inserting in G a new vertex w and replacing the edge uv by the edges uw and wv. A spider is the graph obtained from a star by subdividing all of the edges. A wounded spider is any graph obtained from a spider by removing at least one endvertex. For convenience, let Sk,0 denote any spider with k endvertices, and let Sk,j (1 ≤ j ≤ k) denote the wounded spider obtained from Sk,0 by removing j end-vertices. Observation 1. For paths, cycles, complete multipartite graphs and spiders, (i) γdc (Pn) = ® 1, if n = 1, 2; n− 2, if n ≥ 3. (ii) γdc (Cn) =  1, if n = 3; 2, if n = 4; n− 3, if n ≥ 5. (iii) If k ≥ 2 and n1 ≤ n2 ≤ . . . ≤ nk, then γdc (Kn1,n2,...,nk ) = ® 1, if n1 = 1 2, otherwise. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 5 of 14 (iv) For n ≥ 2 and k ∈ {0, 1, . . . , n}, γdc (Sn,k) = ® n+ 1, if k = 0 n− k + 1, otherwise. Proposition 1. Let G be a connected graph. Then γd(G) ≤ γdc (G) ≤ min{γc(G), 5γd(G)− 4}. (1) Proof. Since connected disjunctive dominating sets are disjunctive dominating sets, the left-hand inequality in (1) follows immediately. Also, since connected dominating sets are connected disjunctive dominating sets, γdc (G) ≤ γc(G). Let S ⊆ V (G) be a γd-set of G, and letm be the number of components in ⟨S⟩. We claim that γdc (G) ≤ γd(G)+4(m−1). If m = 1, then S is a connected disjunctive dominating set of G so that γdc (G) = γd(G) = |S|, and the desired inequality holds. Suppose that m ≥ 2. For distinct components Ci and Cj of ⟨S⟩, define dG(Ci, Cj) = min{dG(u, v) : u ∈ V (Ci), v ∈ V (Cj)}. Let Ci and Cj be distinct components of ⟨S⟩ for which dG(Ci, Cj) is minimum. Let u ∈ V (Ci) and v ∈ V (Cj) for which dG(Ci, Cj) = dG(u, v). Suppose that dG(u, v) ≥ 6, and let P be a u-v geodesic [u = x1, x2, x3, x4, x5, x6, x7, . . . , xn = v] in G. Since S is a disjunctive dominating set of G, in particular, there exists w ∈ S such that dG(w, x4) ≤ 2. If w ∈ Ci, then there exists a w-v geodesic joining Ci and Cj of length less than the length of P . If w /∈ Ci, then there is a w-u geodesic that joins two distinct components of ⟨S⟩ with length shorter than the length of P . Either case is a contradiction to the definitions of Ci and Cj . Thus, dG(u, v) ≤ 5. Put S1 = S ∪ (V (P ) \ {u, v}. Then S1 is a disjunctive dominating set of G with |S1| ≤ |S|+ 4 and ⟨S1⟩ having at most m− 1 components. Repeating the same process in at most (m− 1) times yields a connected disjunctive dominating set Sm−1 with |Sm−1| ≤ |S|+ 4(m− 1). Thus, γdc (G) ≤ γd(G) + 4(m− 1), and the claim is established. Since m ≤ γd(G), we have γdc (G) ≤ γd(G) + 4(γd(G)− 1) = 5γd(G)− 4. If α = min{γc(G), 5γd(G)− 4}, then for G = C5, α = γc(G). For the graph G given in Figure 1, α = 5γd(G)− 4. ............................................................................................................................................................................................. ............................................................................................................................................................................................. ............................................................................................................................................................................................. ............................................................................................................................................................................................. .................................... ............... .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .............. .... .................................... .................................................................................................................................................................. .................................... .......................... ......................... ......................... ......................... ......................... ......................... ........... .................................... ........................................................................................................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................................................................................................................................................. .................................... .......................... ......................... ......................... ......................... ......................... ......................... ........... .................................... ............................................................................................................................................................................................................................. .................................... ....................................• • • • • • • • • • • • • • x1 x2 xk G : ... ... ... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ....... .................................... .................................................................................................................................................................. .................................... .......................... ......................... ......................... ......................... ......................... ......................... ........... .................................... .................................................................................................................................................................................................................................................................................................................... .................................... .................................... Figure 1: A graph G with γc(G) = 5 + k, 5γd(G)− 4 = 6 and γd c (G) = 5 Proposition 2. Let G be a connected graph. Then A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 6 of 14 (i) γdc (G) = 1 if and only if γ(G) = 1. (ii) γdc (G) = 2 if and only if γ(G) ̸= 1 and there exist u, v ∈ V (G) for which uv ∈ E(G) and dG(u, z) ≤ 2 and dG(v, z) ≤ 2 for all z ∈ V (G). In particular, if γc(G) = 2, then γdc (G) = 2. (iii) If G is a tree, then γdc (G) = γc(G). Proof. The proof of statement (i) utilizes (1) in Proposition 1. If γdc (G) = 1, then γd(G) = 1 so that γ(G) = 1. Conversely, if γ(G) = 1, then γc(G) = 1 so that γdc (G) = 1, and (i) holds. Suppose that γdc (G) = 2. By (i), γ(G) > 1. Let {u, v} be a γdc -set of G, and let z ∈ V (G). If z ∈ NG[u], then dG(u, z) ≤ 1 so that dG(v, z) ≤ 2. Similarly, if z ∈ NG[v], then dG(v, z) ≤ 1 so that dG(u, z) ≤ 2. Suppose that z /∈ NG[u]∪NG[v]. Then since {u, v} is a disjunctive dominating set, dG(z, u) = 2 = dG(v, z). Conversely, by (i), γdc (G) ≥ 2. Further, since u and v constitute a connected disjunctive dominating set, γdc (G) = 2, and (ii) holds. To prove (iii), we only have to show that γc(G) ≤ γdc (G). Let S ⊆ V (G) be a γdc -set of G. Suppose NG[S] ̸= V (G), and let x ∈ V (G) \NG[S]. Since S is a disjunctive dominating set, there exist distinct vertices u, v ∈ S for which dG(x, u) = 2 = dG(x, v). Since ⟨S⟩ does not contain a u-v path, ⟨S⟩ is not connected, a contradiction. This shows that S is a connected dominating set of G. Consequently, γc(G) ≤ |S| = γdc (G). Remark 1. The bound given for γdc (G) in Proposition 1 is tight. Indeed, if γ(G) = 1, then γdc (G) = 5γd(G)− 4 = γc(G) = 1. Proposition 3. For every pair of positive integers a and b with 2 ≤ a ≤ b ≤ 2a− 1, there exists a connected graph G for which γd(G) = a and γdc (G) = b. Proof. If a = b = 2, then we take G = P4. Suppose that a = b ≥ 3. Let Pa = [x1, x2, . . . , xa] be a path on a vertices. Obtain G as the graph G1 in Figure 2 by adding • • • • • •....................................................................................................................................... ....................................................................................................................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ....................................... ................................. .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ................................................................................ ............................................ .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... .......................................................... . . . . . . ....................................................................................................................................... ....................................................................................................................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .................................... .................................... ..................................... .................................... ............................................... .................................... .................................... ................. ..... x1 x2 x3 xa−2 xa−1 xa G1 : a1 b1 c1 Figure 2: Graph G for which γd(G) = γd c (G) to Pa the path P j = [xj , aj , bj , cj , xj+1] for each j = 1, 2, . . . , a− 1 such that two distinct P js may intersect but only at a vertex on Pa. Then V (Pa) is both a γd-set and γdc -set of G. Thus, γd(G) = γdc (G) = a. Now, assume that a < b, and let b = a + k, where k ≤ a − 1. If a = k + 1, then b = 2k + 1. In this case, obtain G from P2k+1 as the graph G2 in Figure 3 by adding to P2k+1 = [x1, x2, . . . , x2k+1] the path P j = [xj , aj , bj , cj , xj+2] for each j = 1, 2, . . . , 2k − 1 such that two distinct P js may intersect but only at a vertex on P2k+1. Then γd(G) = A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 7 of 14 • • • • • •.................................... .................................... .................................... .................................................................................................................... ................................................................................ ................................................................................ ................................................................................ .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ....................................... ................................. .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ................................................................................ ............................................ .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... .......................................................... . . . . . . ................................................................................ ................................................................................ ................................................................................ ................................................................................ .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .................................... .................................... ..................................... .................................... ............................................... .................................... .................................... ................. ..... x1 x2 x3 x2k+1 G2 : a1 b1 c1 Figure 3: Graph G with γd(G) = k + 1 and γd c (G) = γd(G) + k k + 1 = a, which is determined by the γd-set {x1, x3, x5, . . . , x2k+1}. Also, γdc (G) = 2k + 1 = b, and V (P2k+1) is a γdc -set of G. Suppose that a = k + 2. Extend the graph G2 in Figure 3 to a graph G = G3 as in Figure 4 by adding P3 = [u, v, x1] through ................................................................................ ................................................................................ ....................................• • • • • • •.................................... .................................... .................................... .................................................................................................................... ................................................................................ ................................................................................ ................................................................................ .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ....................................... ................................. .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... ................................................................................ ............................................ .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... .......................................................... . . . . . . ................................................................................ ................................................................................ ................................................................................ ................................................................................ .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... .................................... .................................... ..................................... .................................... ............................................... .................................... .................................... ................. ..... x1 x2 x3 x2k+1u v G3 : Figure 4: Graph G with γd(G) = k + 2 and γd c (G) = γd(G) + k x1. Then {v, x1, x3, x5, . . . , x2k+1} is a γd-set of G and V (P2k+1) ∪ {v} is a γdc -set of G. Thus, γd(G) = k + 2 = a and γdc (G) = 2k + 2 = b. Finally, suppose that a ≥ k + 3. • • • • • •.................................................................................................... .................................................................................................... .................................... .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... ....................................... ................................. .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... ............................................................... ........................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ................................................ . . . . . . .................................................................................................... .................................................................................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... .................................... .................................... .................................... ...................... .................................... ............................. .................................... .................................... ............ y1 y2 y3 ................................................................ ya−k−1 • • • • • •.................................... .................................... .................................... ................................................................................................... ............................................................... ............................................................... ............................................................... .................................... .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... ....................................... ................................. .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... ............................................................... ........................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ................................................ . . . . . . ............................................................... ............................................................... ............................................................... ............................................................... .................................... .................................... .................................... .................................... .................................... .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... .................................... .......... ......... ......... . .................................... ............... ....... .................................... ...................... .................................... ............................. .................................... .................................... .................................... .................................... ...................... .................................... ............................. .................................... .................................... ............ x1 x2 x3 x2k+1 G4 : Figure 5: Graph G with γd(G) ≥ k + 3 and γd c (G) = γd(G) + k Then a − (k + 1) ≥ 2. Form a graph G∗ 1 similar to the graph G1 in Figure 2 but using Pa−k−1 and obtain G as the graph G4 in Figure 5 by combining G∗ 1 and the graph G2 in Figure 3 by adding the edge y(a−k−1)x1. Then γd(G) = (a − k − 1) + (k + 1) = a and γdc (G) = (a− k − 1) + (2k + 1) = a+ k = b. Corollary 1. The difference γdc (G)− γd(G) can be made arbitrarily large. Proposition 4. For every pair of positive integers a and b with a ≤ b, there exists a connected graph G for which γdc (G) = a and γc(G) = b. Proof. If a = b, then we take, in particular, G = Pa+2. By Observation 1 and Proposition 2(iii), γdc (G) = γc(G) = a = b. Suppose that a < b, say b = a+k, where k ≥ 1. Obtain the graph G from Pa = [x1, x2, . . . , xa], as provided in Figure 6, by adding to Pa the path [x1, aj , bj , cj , x2] for all j = 1, 2, . . . , k. Then V (Pa) and V (Pa)∪{cj : j = 1, 2, . . . , k} are a γdc -set and a γc-set, respectively, of G. Thus, γdc (G) = a and γc(G) = a+ k = b. Corollary 2. The difference γc(G)− γdc (G) can be made arbitrarily large. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 8 of 14 • • • • • • • • ....................................................................................................................................... ....................................................................................................................................... .................................... .................................... .................................... .................................... .......... ......... ......... ......... ......... . .................................... ............... .............. ........ .................................... ..................................... .................................... ............................................... .................................... .................................... ............................................ ............................................. . . ....................................................................................................................................... .................................... .................................... .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ....... .................................... ................. ................ ............. .................................... .............................................. .................................... ........................................................................ .................................... .................................... ... .................................... .................................... ................................................................................................................................................................................................................ .................................... ...................... ..................... ..................... ..................... ..................... ..................... ......... .................................... ........................................................................................................................................ .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .................................... .................................... . . . . . . x1 x2 x3 xa−1 xa G : a1 b1 c1 a2 b2 c2 ak bk ck Figure 6: Graph G for which γc(G) = γd c (G) + k 4. In the Join of Graphs Observation 2. For any graphs G and H, if S ⊆ V (G + H) intersects both V (G) and V (H), then S is a connected dominating set, hence is a connected disjunctive dominating set of G+H. Theorem 1. Let G and H be any graphs, and S ⊆ V (G + H). Then S is a connected disjunctive dominating set of G+H if and only if one of the following holds: (i) S ⊆ V (G) (resp. S ⊆ V (H)) for which either |S| ≥ 2 and ⟨S⟩ is connected or S = {x} where NG[x] = V (G) (resp. NH [x] = V (H)). (ii) S ∩ V (G) ̸= ∅ and S ∩ V (H) ̸= ∅. Proof. Let S be a connected disjunctive dominating set of G +H. Suppose that (ii) does not hold for S, say S ⊆ V (G). The conclusion is obvious for a trivial graph G. Suppose that |V (G)| ≥ 2. If |S| ≥ 2, then ⟨S⟩ is connected subgraph of G. Suppose that |S| = 1, say S = {x}. Since S is a disjunctive dominating set, V (G) = NG[x]. This proves (i). Conversely, suppose that S ⊆ V (G) satisfying property (i). Then V (H) ⊆ NG+H(S). If S = {x} for which NG[x] = V (G), then S is a dominating set, hence a connected disjunctive dominating set of G+H. Suppose that |S| ≥ 2. Let x ∈ V (G)\S, and suppose that x /∈ NG(S). Pick any distinct u, v ∈ S. Then dG+H(x, u) = 2 = dG+H(x, v). Thus, S is a disjunctive dominating set of G +H. Since ⟨S⟩ is connected, the conclusion follows. Similarly, if S ⊆ V (H) for which either |S| ≥ 2 and ⟨S⟩ is connected or S = {x} where NH [x] = V (H), then S is a connected disjunctive dominating set of G+H. Observation 2 finally establishes the necessity proof. Corollary 3. For nontrivial graphs G and H, γdc (G+H) = min{γ(G), γ(H), 2}. 5. In the Corona of Graphs In a corona G◦H, we denote by Hv that copy of H which is being joined to the vertex v of G. We also denote by Hv + v that subgraph ⟨{v} ∪ V (Hv)⟩ of G ◦ H induced by A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 9 of 14 {v} ∪ V (Hv). Thus, V (G ◦H) = V (G) ∪ ( ∪v∈V (G)V (Hv) ) . Theorem 2. [4] Let G be a nontrivial connected graph and H any graph, and let S ⊆ V (G ◦ H). Then S is a disjunctive dominating set of G ◦ H if and only if each of the following holds for S: (i) |S ∩NG(v)| ≥ 2 for all v ∈ V (G) \ S with S ∩ V (Hv) = ∅; (ii) |S ∩ V (Hv)| ≥ 1 for all v ∈ V (G) \ S with |S ∩NG(v)| = 1; and (iii) S ∩ V (Hv) is a disjunctive dominating set of Hv + v for all v ∈ V (G) \ S with S ∩NG(v) = ∅. In particular, if γ(H) > 1, then |S ∩ V (Hv)| ≥ 2. Proposition 5. Let G be a nontrivial connected graph and let H be any graph. Then a set S ⊆ V (G ◦H) is a connected disjunctive dominating set of G ◦H if and only if S = A ∪ (∪v∈ASv) , (2) where A is a connected 2-dominating set of G and Sv ⊆ V (Hv) for all v ∈ A. Proof. Let S ⊆ V (G ◦ H) be a connected disjunctive dominating set of G ◦ H. Put A = S ∩ V (G) and Sv = S ∩ V (Hv) for each v ∈ V (G). Then S = A ∪ (∪v∈ASv) ∪ ( ∪v∈V (G)\ASv ) . Since G is nontrivial and ⟨S⟩ is connected, A ̸= ∅ and ⟨A⟩ is connected. We claim that Sv = ∅ for all v ∈ V (G) \ A, and Equation (2) holds. Suppose v ∈ V (G) \ A for which Sv ̸= ∅. Since ⟨S⟩ is connected, S = Sv. This is impossible because A ̸= ∅. Hence, Sv = ∅. Consequently, |A ∩NG(v)| ≥ 2 by Theorem 2(i). Thus, S = A ∪ (∪v∈ASv) and A is a (connected) 2-dominating set of G. Conversely, assume that S has the form given in Equation 2, where A is a connected 2- dominating set of G and Sv ⊆ V (Hv) for each v ∈ A. Then |S∩NG(v)| = |A∩NG(v)| ≥ 2 for each v ∈ V (G) \ S. By Theorem 2, S is a disjunctive dominating set of G ◦H. Since Sw = ∅ for all w ∈ V (G) \ A and ⟨A⟩ is connected, it follows that ⟨S⟩ is connected. Therefore, S is a connected disjunctive dominating set of G ◦H. Lemma 1. Let G be a connected graph of order n ≥ 2. (i) γ×2,c(G) = 2 if and only if G = K2 or G = K2 +H for some graph H. (ii) γ×2,c(G) = n if and only if for every v ∈ V (G), v is either an end-vertex or a cut-vertex. (iii) γ×2,c(G) = n− 1 if and only if (a) G has a non-cut vertex with degree at least two, and A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 10 of 14 (b) for each non-cut vertex v ∈ V (G) with degG(v) ≥ 2, if w is a non-cut vertex of H = ⟨V (G) \ {v}⟩ with degH(w) ≥ 2, then degG(v) = 2 and w ∈ NG(v). Proof. (i) Suppose γ×2,c(G) = 2. If n = 2, then G = K2. Suppose n ≥ 3. Let S = {a, b} be a γ×2,c-set of G. Since ⟨S⟩ is connected, it follows that ab ∈ E(G). Let G1 = ⟨{a, b}⟩ and H = ⟨V (G) \ {a, b}⟩. Let h ∈ V (H). Since S is a 2-dominating set, h ∈ NG(a) ∩NG(b). Thus, G = G1 +H ∼= K2 +H. The converse is clear. (ii) Suppose γ×2,c(G) = n. Let v ∈ V (G). Suppose v is neither an end-vertex nor a cut-vertex. Then S = V (G) \ {v} is a connected 2-dominating set of G. This implies that γc2(G) ≤ |S| = n− 1, contrary to our assumption. Thus, v is end-vertex or a cut-vertex of G. For the converse, suppose that every v ∈ V (G) is either an end-vertex or a cut-vertex. Let End(G) denote the set of all end-vertices of G and let S be a γ×2,c-set of G. Since S is a 2-dominating set, End(G) ⊆ S. Suppose S ̸= V (G), say x ∈ V (G) \ S. Then x is a cut-vertex of G. Since S ⊆ V (G) \ {x} and ⟨S⟩ is connected, S ⊆ V (CS) for some component CS of ⟨V (G) \ S⟩. Let C be a component of ⟨V (G) \ S⟩ different from CS and let z ∈ V (C). Then NG(z)∩ S = ∅, contrary to the assumption that S is a 2-dominating set. Thus, S = V (G) and γ×2,c(G) = n, showing that (ii) holds. (iii) Suppose γ×2,c(G) = n− 1 and let S = V (G) \ {v} be a γ×2,c-set of G. Then v is a non-cut vertex and degG(v) ≥ 2. Let H = ⟨V (G)\{v}⟩ and suppose there exists a non-cut- vertex w ∈ V (H) with degH(w) ≥ 2. Suppose that w /∈ NG(v). Then S′ = V (G) \ {v, w} is a connected 2-dominating set of G, contrary to the assumption that S is a γ×2,c-set. Hence, w ∈ NG(v). Suppose degG(v) ≥ 3. Then, again, V (G) \ {v, w} is a connected 2-dominating set of G, a contradiction. Therefore, degG(v) = 2. For the converse, suppose G satisfies (a) and (b). If n = 3, then G = C3 = K3 and γ×2,c(G) = 2. Suppose n ≥ 4 and let S be a γ×2,c-set of G. By (a), |S| ≤ n − 1. Let v ∈ V (G) \ S. Since ⟨S⟩ is a connected 2-dominating set, it follows that v is a non- cut-vertex of G and degG(v) ≥ 2. Suppose there exists w ∈ V (G) \ (S ∪ {v}). Then w is also non-cut-vertex of G and |NG(w) ∩ S| ≥ 2. Hence, w is a non-cut-vertex of H = ⟨V (G) \ {v}⟩ and deg(w) ≥ 2. By (b), it follows that vw ∈ E(G) and degG(v) = 2. Thus, |NG(v)∩S| ≤ 1, contrary to the assumption that S is a 2-dominating set. Therefore, S = V (G) \ {v} and γ×2,c(G) = |S| = n− 1. The next result is immediate from Proposition 5 and Lemma 1. Corollary 4. Let G be a connected graph of order n and let H be any graph. Then γdc (G ◦H) = γ×2,c(G). In particular, the following hold: (i) If G = Kn with n ≥ 2, then γdc (G ◦H) = 2. (ii) If G is a tree, then γdc (G ◦H) = n. (iii) If G = Cn with n ≥ 3, then γdc (G ◦H) = n− 1. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 11 of 14 6. In the lexicographic product of graphs For any graphs G and H and for any C ⊆ V (G[H]), there exists S ⊆ V (G) for which C = ∪x∈S ({x} × Tx), where Tx ⊆ V (H) for each x ∈ S. Moreover, if ⟨C⟩ is connected, then so is ⟨S⟩. Provided |S| ≥ 2, the converse is also true. For convenience, we write Nd G[S] = S ∪Nd G(S). Theorem 3. [4] Let G and H be nontrivial connected graphs, and let C = ∪x∈S ({x} × Tx). Then C is a disjunctive dominating set of G[H] if and only if one of the following holds: (i) S is a disjunctive total dominating set in G; (ii) S is a distance-two dominating set of G satisfying the following: (a) For each x ∈ V (G) \ Nd G[S] there exists u ∈ S for which dG(u, x) = 2 and |Tu| ≥ 2. (b) For each x ∈ S \ NG(S, 2), either Tx = {y} and is a dominating set of H or |Tx| ≥ 2. Theorem 4. Let G and H be nontrivial connected graphs, and let C = ∪x∈S ({x} × Tx). Then C is a connected disjunctive dominating set of G[H] if and only if one of the following holds for S: (i) |S| ≥ 2 and S is a connected disjunctive dominating set of G; (ii) S is a connected distance-two dominating set of G satisfying exactly one of the following: (a) |S| ≥ 2 and for each x ∈ V (G)\Nd G[S] there exists u ∈ S for which dG(u, x) = 2 and |Tu| ≥ 2. (b) S = {x} for some x ∈ V (G), where ⟨Tx⟩ is a connected graph satisfying the following: (b.1) If S is a non-dominating set of G, then |Tx| ≥ 2; and (b.2) If |Tx| = 1, then S and Tx are dominating sets of G and H, respectively. Proof. Suppose that C is a connected disjunctive dominating set ofG[H]. As previously remarked, ⟨S⟩ is a connected graph. First, if Theorem 3(i) holds for S, then |S| ≥ 2 and S is a disjunctive dominating set of G. In this case, (i) holds. Next, suppose that Theorem 3(ii) holds for S. Then S is a connected distance-two dominating set of G. If |S| ≥ 2, then condition (ii)(a) follows immediately from Theorem 3(ii)(a). Assume that S = {x} for some x ∈ V (G). Clearly, ⟨Tx⟩ is connected as ⟨C⟩ is connected. Suppose S is a nondominating set of G, and choose u ∈ V (G) \ NG[x]. For any v ∈ V (H), there exist distinct y, z ∈ Tx such that dG[H] ((u, v), (x, y)) = 2 = dG[H] ((u, v), (x, z)). Thus, |Tx| ≥ 2, and (ii)(b)(b.1) holds. Now, if |Tx| = 1, say Tx = {y}, then C = {(x, y)} is a dominating set of G[H]. Necessarily, S and {y} are dominating sets of G and H, respectively. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 12 of 14 Conversely, if (i) holds for S, then S is a disjunctive total dominating set of G. Conse- quently, C is a disjunctive dominating set of G[H] by Theorem 3. Since ⟨S⟩ is connected, ⟨C⟩ is connected. Assume that S is a connected distance-two dominating set of G. Suppose that condition (ii)(a) holds for S. Then ⟨C⟩ is connected. Let (x, y) ∈ V (G[H]) \ C. Case 1: x ∈ Nd G[S] If u ∈ S ∩NG(x), then (x, y)(u, v) ∈ E(G) for any v ∈ Tu. Suppose that x /∈ NG(S). Then there exist distinct u,w ∈ S for which dG(x, u) = 2 = dG(x,w). Pick v ∈ Tu and z ∈ Tw. Then (u, v), (w, z) ∈ C and dG[H] ((x, y), (u, v)) = 2 = dG[H] ((x, y), (w, z)). Case 2: x /∈ Nd G[S] By the hypothesis, there exists u ∈ S for which dG(u, x) = 2 and |Tu| ≥ 2, say v, z ∈ Tu. Then (u, v) and (u, z) are distinct vertices in C and dG[H] ((x, y), (u, v)) = 2 = dG[H] ((x, y), (u, z)). The above cases imply that C is a connected disjunctive dominating set of G[H]. Finally, suppose that |S| = 1, say S = {x}, satisfying condition (ii)(b). Then ⟨C⟩ = ⟨{x} × Tx⟩ is connected. Let (u, v) ∈ V (G[H]) \ C. Case 1: u ̸= x If ux ∈ E(G), then (u, v)(x, y) ∈ E(G[H]) for any y ∈ Tx. If dG(u, x) = 2, then by condition (b.1), |Tx| ≥ 2, say y, z ∈ Tx. Then (x, y), (x, z) are distinct vertices in C with dG[H] ((x, y), (u, v)) = 2 = dG[H] ((x, z), (u, v)). Case 2: u = x Note that since G is nontrivial, dG[H] ((u, v), (x, y)) ≤ 2 for all y ∈ Tx. If |Tx| ≥ 2, then (u, v) ∈ Nd G[H](C). On the other hand, if Tx = {y}, then by condition (b.2), vy ∈ E(H) so that (u, v)(x, y) ∈ E(G[H]). Accordingly, C is a connected disjunctive dominating set of G[H]. Let S ⊆ V (G) be a distance-two dominating set of G. For each x ∈ V (G) \Nd G[S], let sx ∈ S ∩NG(x, 2). We define for S, Sd = {sx : x ∈ V (G) \Nd G[S]}. Denote by CD2D(G) the families of all connected distance-two dominating sets of G. Corollary 5. Let G and H be nontrivial connected graphs. Then (i) Provided γ2,c(G) = 1, γdc (G[H]) = ® 1, if γ(H) = 1 = γ(G) 2, if γ(G) ≥ 2. (ii) Provided γ2,c(G) ≥ 2, γdc (G[H]) = min{γdc (G), α(G)}, where α(G) = min{|S \ Sd|+ 2|Sd| : S ∈ CD2D(G)}. For all nontrivial connected graphs H, γdc (C4[H]) = 2, γdc (C6[H]) = γdc (C6) = 3 and γdc (P6[H]) = α(P6) = 4. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 13 of 14 Acknowledgements This research work is fully supported by the Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST- ASTHRDP), Philippines; the Office of the Vice Chancellor for Research and Enterprise (OVCRE) of the MSU-Iligan Institute of Technology of the Philippines; and the MSU - Tawi-Tawi College of Technology and Oceanography, Philippines. The authors would also like to recognize the efforts of the anonymous reviewers whose suggestions and recommendations contributed to the improvement of the paper. References [1] W. Goddard, M. A. Henning, and C. A. McPillan. The disjunctive domination number of a graph. Quaestiones Mathematicae, 37:547–561, 2014. [2] M. A. Henning and V. Naicker. Disjunctive total domination in graphs. Combinatorial Optimization, 31:1090–1110, 2016. [3] M. A. Henning and V. Naicker. Bounds on the disjunctive total domination number of a tree. Discussiones Mathematicae Graph Theory, 36:153–171, 2016. [4] F. Jamil and R. Malalay. On disjunctive domination in graphs. Quaestiones Mathe- maticae, 43(2):149–168, 2020. [5] R. Malalay and F. P. Jamil. Restrained disjunctive domination in graphs under some binary operations. European Journal of Pure and Applied Mathematics, 15(1):207– 223, 2022. [6] F. Buckley and F. Harary. Distance in Graphs. Addison-Wesley, Redwood City, CA, 1990. [7] C. Berge. Théorie des graphes et ses applications. Dunod, Paris, 1958. Translation: The theory of Graphs and its Applications, Methuen (London) and Wiley (New York), 1962. [8] E. Cockayne and S. Hedetniemi. Towards a theory of domination in graphs. Networks, 7(3):247–261, 1977. [9] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York, 1998. [10] O. Ore. Theory of graphs, volume 38 of Amer. Math. Soc. Colloq. Publ. Amer. Math. Soc., Providence, RI, 1962. [11] E. Cockayne, R. M. Dawes, and S. T. Hedetniemi. Total domination in graphs. Networks, 10(3):211–219, 2006. [12] W. J. Desormeaux, T. W. Haynes, and M. A. Henning. An extremal problem for total domination stable graphs upon edge removal. Discrete Applied Mathematics, 159:1048–1052, 2011. [13] M. Henning and A. Yeo. Total Domination in Graphs. Springer, New York, 2013. [14] S. Bermudo, J. C. Hernandez-Gomez, and J. M. Sigarreta. On the total k-domination in graphs. Discussiones Mathematicae Graph Theory, 38:301–317, 2018. A. Aradais, F. Jamil, S. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6939 14 of 14 [15] M. Chellali. Bounds on the 2-domination number in cactus graphs. Opuscula Math- ematica, 26(1), 2006. [16] B. D. Domolan and S. R. Canoy Jr. 2-domination and restrained 2-domination in graphs. Applied Mathematical Sciences, 9(114):5651–5659, 2015. [17] A. Hansberg and L. Volkmann. Note on graphs with equal domination and 2- domination numbers. Discrete Mathematics, 308:2277–2281, 2008. [18] A. P. Kazemi. On the total k-domination number of graphs. Discussiones Mathe- maticae Graph Theory, 32:419–426, 2012. [19] C. Sivagnanam. Neighborhood total 2-domination in graphs. International Journal of Mathematics and Combinatorics, 4:108–119, 2014. [20] N. Sridharan, V. S. A. Subramanian, and M. D. Elias. Bounds on the distance two- domination number of a graph. Graphs and Combinatorics, 18:667–675, 2002. [21] F. Tian and J-M Xu. On distance connected domination numbers of graphs. Ars Combinatoria, 84, 2007.