EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 15, No. 3, 2022, 1217-1228 ISSN 1307-5543 – ejpam.com Published by New York Business Global Supercliques in a Graph Ramil H. Dela Cerna1,∗, Sergio R. Canoy, Jr.1 1 Department of Mathematics and Statistics, College of Science and Mathematics, Center for Graph Theory, Algebra and Analysis-PRISM, MSU-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. A set S ⊆ V (G) of a (simple) undirected graph G is a superclique in G if it is a clique and for every pair of distinct vertices v, w ∈ S, there exists u ∈ V (G) \ S such that u ∈ NG(v) \ NG(w) or u ∈ NG(w) \ NG(v). The maximum cardinality among the supercliques in G, denoted by ωs(G), is called the superclique number of G. In this paper, we determine the superclique numbers of some graphs including those resulting from some binary operations of graphs. We will also show that the difference of the clique number and the superclique number can be made arbitrarily large. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Clique, clique number, superclique, superclique number 1. Introduction Clique is one of the basic concepts in graph theory. This concept was used in many mathematical problems and constructions on graphs. The term clique was introduced by Luce and Perry [12]. In a study in [8], Gaquing and Canoy characterized the cliques in the lexicographic and Cartesian products of graphs. From the characterizations, the corresponding clique numbers of these graphs have been subsequently determined. Some studies involving cliques can be found in [5], [6], [14], and [17]. With the objective of identifying the exact location of an intruder in a network, Slater [19] introduced the concepts of resolving set and metric dimension. These concepts were independently considered by Harary and Melter in [10]. Later, Chartrand et al. (see [4]) also studied resolving set and metric dimension of a graph. Oellermann and Fransen [15] considered the metric dimension of Cartesian products of graphs. It is known that the problem of finding the metric dimension of a graph is NP-hard (see [9]). In 2003, Brigham et al. [2] combined the concepts of resolving and domination. In their article, they defined ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v15i3.4480 Email addresses: ramil.delacerna@g.msuiit.edu.ph (R. Dela Cerna), sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) https://www.ejpam.com 1217 © 2022 EJPAM All rights reserved. R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1218 resolving dominating set as a set that is both resolving and dominating. Along with the concept, they also studied the parameter called resolving domination number of a graph. A more restrictive concept of resolving set, called strong resolving set, and its associ- ated invariant (the strong metric dimension) were introduced in [18]. The invariant was revisited and studied by Oellermann and Fransen in [16] for graphs and digraphs. Recently, Acal, Sumaoy, and Rara in [1], [13], and [20] investigated the concepts of strong connected resolving domination and restrained resolving domination of graphs under some binary operations. In these studies, they specifically introduced the concept of superclique and determined the values of the invariants for the join and corona, and lexicographic product of two graphs in terms of the superclique number of a graph. This work is therefore mo- tivated by the recent studies on these variations of strong resolving set and strong metric dimension that utilize the concepts of superclique and superclique number. Other works on graph-theoretic parameters that involved some binary operations can be found in [3], [7], and [11]. 2. Terminologies and Notations Let G = (V (G), E(G)) be a simple undirected graph. The distance between two vertices u and v of G, denoted by dG(u, v), is equal to the length of a shortest path connecting u and v. Any path connecting u and v of length dG(u, v) is called a u-v geodesic. The open neighbourhood of a vertex v of G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} and its closed neighbourhood is the set NG[v] = NG(v) ∪ {v}. The open neighbourhood of a subset S of V (G) is the set NG(S) = ∪v∈SNG(v) and its closed neighbourhood is the set NG[S] = NG(S) ∪ S. The degree of v, denoted by degG(v), is equal to |NG(v)|. A set S ⊆ V (G) is a dominating set of G if NG[S] = V (G). The smallest cardinality of a dominating set of G, denoted by γ(G), is called the domination number of G. A dominating set of G with with cardinality γ(G) is called a γ-set of G. A set S ⊆ V (G) is a clique in a graph G if the graph G[S] induced by S is a complete subgraph of G. A clique C in G is called a superclique if for every pair of distinct vertices u, v ∈ C, there exists w ∈ V (G)\C such that w ∈ NG(u)\NG(v) or w ∈ NG(v)\NG(u). A superclique C inG is called a point-wise non-dominated superclique if for every u ∈ C, there exists v ∈ V (G) \C such that uv /∈ E(G). A superclique (resp. point-wise non-dominated superclique) C is maximum in G if |C| ≥ |C ′| for all supercliques (resp. pointwise non- dominated supercliques) C ′ in G. The superclique number (resp. pointwise non-dominated superclique number), denoted by ωS(G) (resp. ωpnds(G)) of G is the cardinality of a maximum superclique (resp. maximum pointwise non-dominated superclique) in G. The shadow graph S(G) of a graph G is the graph obtained by taking two copies of G, say G1 and G2, and joining each vertex u ∈ V (G1) to the neighbors of the corresponding vertex u′ ∈ V (G2). For a graph G, the complementary prism, denoted by GG, is formed from the disjoint union of G and its complement G by adding a perfect matching between corresponding vertices of G and G. For each v ∈ V (G), let v denote the vertex corre- sponding to v in G. In simple terms, the graph GG is formed from G ∪G by adding the edge vv for every vertex v ∈ V (G). R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1219 Let G and H be graphs. The join of G and H, denoted by G +H is the graph with vertex set V (G+H) = V (G)∪ V (H) and edge set E(G+H) = E(G)∪E(H)∪ {uv : u ∈ V (G), v ∈ V (H)}. The corona of G andH, denoted by G◦H, is the graph obtained from G by taking a copy Hv of H and forming the join ⟨v⟩+Hv = v+Hv for each v ∈ V (G). The lexicographic product of graphs G and H, denoted by G[H], is the graph with vertex set V (G[H]) = V (G)×V (H) such that (v, a)(u, b) ∈ E(G[H]) if and only if either uv ∈ E(G) or u = v and ab ∈ E(H). The Cartesian product of G and H, denoted by G□H, is the graph with vertex set V (G[H]) = V (G) × V (H) such that (v, a)(u, b) ∈ E(G[H]) if and only if either uv ∈ E(G) and a = b or u = v and ab ∈ E(H). We note that every non-empty subset C of V (G) × V (H) can be expressed as C = ∪x∈S [{x} × Tx], where S ⊆ V (G) and Tx = {a ∈ V (H) : (x, a) ∈ C} for each x ∈ S. 3. Results Two adjacent vertices v and w of a graph G are true twins if NG[v] = NG[w]. Theorem 1. Let G be any graph. Then each of the following statements holds: (i) G admits a superclique and 1 ≤ ωs(G) ≤ ω(G). (ii) ωs(G) = 1 if and only if every component of G is complete. (iii) ωs(G) = ω(G) if and only if G has a maximum clique containing no true twin vertices. Proof. G admits a superclique because every singleton subset of V (G) is a superclique in G. Moreover, since every superclique is a clique, (i) holds. Suppose that ωs(G) = 1. Suppose further that G has a component H which is not complete. Then there exist vertices x, y ∈ V (H) such that dH(x, y) = dG(x, y) = 2. Let z ∈ NG(x) ∩ NG(y). Then S = {x, z} is a superclique in G. Hence, ωs(G) ≥ |S| = 2 > 1, contrary to our assumption that ωs(G) = 1. Thus, every component of G is complete. The converse is easy. Next, suppose that ωs(G) = ω(G). Let S be a superclique in G such that |S| = ωs(G). The assumption ωs(G) = ω(G) would imply that S is a maximum clique of G. Suppose S contains true twin vertices, say v and w. Then (V (G) \ S) ∩ (NG(v) \NG(w)) = (V (G) \ S) ∩ (NG(w) \NG(v)) = ∅, contrary to the assumption that S is a superclique in G. Thus, S does not contain true twin vertices. Conversely, suppose that G has a maximum clique S containing no true twin vertices. Then clearly, S is a superclique in G. This implies that ωs(G) = ω(G). Remark 1. Each of the following statements holds: (i) For any positive integer n, ωs(Kn) = 1. R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1220 (ii) For any positive integer n ≥ 2, ωs(Pn) = { 1 if n = 2 2 if n ≥ 3. (iii) For any positive integer n ≥ 3, ωs(Cn) = { 1 if n = 3 2 if n ≥ 4. Theorem 2. Let a and b be positive integers such that 2 ≤ a ≤ b. Then there exists a connected graph G such that ωs(G) = a and ω(G) = b. Proof. Consider the following cases: Case 1. a = b. Consider the graph G in Figure 1 obtained from the complete graph Ka by adding the a pendant vertices. Then clearly, ωs(G) = ω(G) = a. .................................... .................................... .................................... .................................... ........................................................................ .................................... ........................................................................ .................................... ........................................................................ .................................... .................................... .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. .................................................................................................................................................................. ..................................................................................................................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. .................................................................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ........................................................................................................ ..................................................................................................................................... ........................................................................................................ ................................................................................................................................................ .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. • • • ..................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................ ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........... xa x2 x3 x4 x5 x1 G : Figure 1: A graph G with ωs(G) = ω(G) Case 2. a < b. Consider the graph G in Figure 2 where G[{x1, x2, . . . , xa}] = Ka and G[{y1, y2, . . . , yb}] = Kb. Let S1 = {x1, x2, . . . , xa} and S2 = {y1, y2, . . . , yb}. Clearly, S2 is the (only) maximum clique in G and so ω(G) = b. Since S2 has true twin vertices, it is not a superclique in G (hence, ωs(G) ̸= ω(G)) by Theorem 1(iii). Also, the only subsets of S2 that are supercliques in G are the singletons and the sets {y1, yi} where i ∈ {2, 3, . . . , b}. It can easily be verified that S1 is a maximum superclique in G. Consequently, ωs(G) = a. R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1221 .................................... .................................... .................................... .................................... ........................................................................ .................................... ........................................................................ .................................... .................................... .................................... .................................... .................................... .................................... ........................................................................ .................................... ........................................................................ .................................... .................................... .................................... .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. .................................................................................................................................................................. ..................................................................................................................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. .................................................................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ........................................................................................................ ..................................................................................................................................... ........................................................................................................ ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. • • • • • • ..................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........................................................................................................................................................................................................................................................................................ ................................................................................................................................................................................................................................................................................ ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........... ............................................................................................................................................................................................... ..................................................................................................................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .. ............................................................................................................................................................................................... ............................................................................................................................. ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .... ........................................................................................................................................................................................................................................................................................................... ...................................................................................................................................................................................................................................................................................................................................................................... ............................................................................................................................................................................................................................................................................................................................................................................................................ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ..... ............................................................................................................................................................................................................................................ ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ....... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ........ .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ....... ...................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ............ .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... . .............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ............. ...... ........................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... .......................... ............................................................................................................................................................................................................................................................................................................................................................... ...................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... ..................... .................................................................................................................................................................................................................................................................................................................................................................. ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ .......................................................................................................................................................................................................................................................................................................................................................... ....................................................................................................................................................................................................................................... xa x2 x3 x4 x5 x1 = y1 y2 y3 y4 y5y6 y7 yb G∗ : Figure 2: A graph G with ωs(G) < ω(G) Therefore, the assertion holds. Corollary 1. Let n be a positive integer. Then there exists a connected graph G such that ω(G)− ωs(G) = n. In other words, the difference ω − ωs can be made arbitrarily large. Proof. Let n be a positive integer. By Theorem 2, there exists a connected graph G with ωs(G) = n+ 1 and ω(G) = 2n+ 1. Thus, ω(G)− ωs(G) = n. Theorem 3. Let G be a non-trivial connected graph and let G1 and G2 be two copies of G in the definition of S(G). Then C is a superclique in S(G) if and only if one of the following holds: (i) C is a clique in G1. (ii) C is a clique in G2. (iii) C = CG1 ∪ CG2, where CG1 and CG2 are cliques in G1 and G2, respectively, and satisfy the following conditions: (a) v′ /∈ CG2 whenever v ∈ CG1, and (b) vw ∈ E(G1) for each v ∈ CG1 and w′ ∈ CG2. R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1222 Proof. Let C be a superclique in S(G) and set CG1 = C∩V (G1) and CG2 = C∩V (G2). If CG2 = ∅ or CG1 = ∅, then (i) or (ii) holds. So suppose that CG1 ̸= ∅ and CG2 ̸= ∅. Then CG1 and CG2 are cliques in G1 and G2, respectively. Let v ∈ CG1 . Then vv′ /∈ V (S(G)) by definition of S(G). Hence, v′ /∈ CG2 , showing that (a) holds. Next, let v ∈ CG1 and w′ ∈ CG2 . Since C is a clique in S(G), vw′ ∈ E(S(G)). The definition of S(G) will now imply that vw ∈ E(G1) showing that (b) holds. Therefore, (iii) holds. For the converse, suppose that (i) holds. Let v, w ∈ C with v ̸= w. Then v′ ∈ V (S(G)) \ C and v′ ∈ NS(G)(w) \ NS(G)(v) by the adjacency in S(G). Hence, C is a superclique in S(G). The same conclusion can be made if (ii) holds. Next, suppose that (iii) holds. Then, by (a) and (b), C is a clique of S(G). Let x, y ∈ C with x ̸= y. If x, y ∈ CG1 , then x′ ∈ V (S(G)) \ C by (a) and x′ ∈ NS(G)(y) because xy ∈ E(G1). It follows that x ′ ∈ NS(G)(y) \NS(G)(x). Suppose x, y ∈ CG2 , say x = v′ and y = w′ where v, w ∈ V (G1). Then v ∈ V (S(G)) \ C by (a) and v ∈ NS(G)(w ′) because v′w′ ∈ E(G2). Hence, v ∈ NS(G)(w ′) \ NS(G)(v ′). Suppose x ∈ CG1 and y ∈ CG2 , say y = z′, where z ∈ V (G1). By (b), z ∈ [V (S(G))\C]∩NG(x). Thus, z ∈ NS(G)(x)\NS(G)(y). This shows that C is a superclique in S(G). Corollary 2. Let G be a connected graph. Then ωs(S(G)) = ω(G). Proof. If G = K1, then S(G) = K2 (empty graph). It follows that ωs(S(G)) = ω(G) = 1. Next, suppose that G is non-trivial. Let C be a superclique in S(G) of the form given in Theorem 3(iii). Then C = CG1 ∪ CG2 , where CG1 and CG2 are cliques in G1 and G2, respectively, and satisfy conditions (a) and (b). Set C∗ G1 = {v ∈ V (G1) : v ′ ∈ CG2}. Then |C∗ G1 | = |CG2 |. By condition (a), CG1 ∩ C∗ G1 = ∅. Let C∗ = CG1 ∪ C∗ G1 and let x, y ∈ C∗ with x ̸= y. If x, y ∈ CG1 , then xy ∈ E(G1). Suppose x, y ∈ C∗ G1 . Then x′, y′ ∈ CG2 . Since CG2 is a clique in G2, x ′y′ ∈ E(G2). This implies that xy ∈ E(G1). Finally, suppose that x ∈ CG1 and y ∈ C∗ G1 . Then y′ ∈ CG2 . By condition (b), it follows that xy ∈ E(G1). Therefore, C∗ is a clique in G1 and |C| = |C∗| ≤ ω(G1) = ω(G). The desired result now follows from Theorem 3. Theorem 4. Let G be a non-trivial graph. Then C is a superclique in GG if and only if one of the following holds: (i) C is a clique in G. (ii) C is a clique in G. (iii) C = {v, v} for some v ∈ V (G). Proof. Let C be a superclique in GG and set CG = C ∩ V (G) and CG = C ∩ V (G). If CG = ∅ or CG = ∅, then C is a clique in G or G, showing that (i) or (ii) holds. Suppose that CG ̸= ∅ and CG ̸= ∅. Let v ∈ CG and w ∈ CG. Since C is a clique, vw ∈ E(GG). R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1223 Hence, by definition of GG, w = v. Now, because v /∈ NGG(u) for all u ∈ NG(v), it follows that CG = {v}. Similarly, CG = {v}. Thus, C = {v, v}, showing that (iii) holds. For the converse, suppose first that (i) holds. Then C is a clique in GG. Let p, q ∈ C with p ̸= q. Then p ∈ NGG(p) \NGG(q). This implies that C is a superclique in GG. The same conclusion holds if (ii) is assumed. Suppose now that (iii) holds, i.e., C = {v, v} for some v ∈ V (G). Pick any w ∈ V (G) \ {v}. If w ∈ NG(v), then w ∈ NGG(v) \NGG(v). If w /∈ NG(v), then w ∈ NGG(v) \NGG(v). Thus, C is a superclique in GG. The next results are immediate from Theorem 4. Corollary 3. Let G be a non-trivial graph. Then ωs(GG) = max{2, ω(G), ω(G)}. Corollary 4. Let G be any graph. Then C is a superclique in GG if and only if it is a clique in GG. In particular, ωs(GG) = ω(GG). Theorem 5. Let G and H be any two graphs. Then C ⊆ V (G +H) is a superclique in G+H if and only if one of the following statements holds: (i) C is a superclique in G. (ii) C is a superclique in H. (iii) C = CG ∪ CH , where CG and CH are supercliques in G and H, respectively, and at least one of them is pointwise non-dominated. Proof. Suppose C is a superclique in G+H. Set CG = C ∩V (G) and CH = C ∩V (H). If one of CG and CH is empty, say CH = ∅, then clearly, CG is a superclique in G. Thus, (i) or (ii) holds. Suppose that CG ̸= ∅ and CH ̸= ∅. Since C is a clique, CG and CH are cliques in G and H, respectively. Let v, w ∈ CG such that v ̸= w. Since C is a superclique in G+H, there exists z ∈ V (G+H) \ C such that z ∈ NG+H(v) \NG+H(w) or z ∈ NG+H(w) \ NG+H(v). Since V (H) \ CH ⊆ NG+H(v) ∩ NG+H(w), it follows that z ∈ V (G) \ CG. Hence, z ∈ NG(v) \NG(w) or z ∈ NG(w) \NG(v), showing that CG is a superclique in G. Similarly, CH is a superclique in H. Suppose now that both CG and CH are not pointwise non-dominated supercliques in G and H, respectively. Then there exist a ∈ CG and b ∈ CH such that V (G) \ CG ⊆ NG(a) and V (H) \ CH ⊆ NG(b). This would imply that V (G+H) \C ⊆ NG+H(a)∩NG+H(b), contradicting the assumption that C is a superclique in G+H. Therefore, CG or CH is a pointwise non-dominated superclique, showing that (iii) holds. For the converse, suppose that (i) or (ii) holds. Then clearly, C is a superclique in G+H. Next, suppose that (iii) holds, i.e., C = CG ∪CH and satisfies the given property. Assume that CH is a pointwise non-dominated superclique in H. Let v, w ∈ V (G+H)\C such that v ̸= v. Suppose first that v, w ∈ CG. Since CG is a superclique in G, there exists y ∈ V (G) \ CG such that y ∈ NG(v) \ NG(w) or y ∈ NG(w) \ NG(v). Hence, R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1224 y ∈ V (G+H) \ C and y ∈ NG+H(v) \NG+H(w) or y ∈ NG+H(w) \NG+H(v). Similarly, if v, w ∈ V (H) \ CH , then there exists p ∈ V (G +H) \ C and p ∈ NG+H(v) \ NG+H(w) or p ∈ NG+H(w) \ NG+H(v). Suppose now that v ∈ CG and w ∈ CH . Since CH is pointwise non-dominated, there exists q ∈ V (H) \ CH such that q /∈ NH(v). It follows that q ∈ NG+H(v) \NG+H(w). Accordingly, C is a superclique in G+H. Corollary 5. Let G be a non-complete graph and let n be a positive integer. Then C ⊆ V (Kn+G) is a superclique in Kn+G if and only if one of the following statements holds: (i) C is a superclique in G. (ii) C = {p} for some p ∈ V (Kn). (iii) C = CG∪{p} for some pointwise non-dominated superclique CG in G and p ∈ V (Kn). Proof. Since the only supercliques in Kn are the singleton subsets of V (Kn) and none of these sets is pointwise non-dominated, C ⊆ V (Kn + G) is a superclique in Kn + G if and only if (i), (ii), or (iii) holds by Theorem 5. The next result is a consequence of Theorem 5 and Corollary 5. Corollary 6. Let G and H be any two graphs and let n be a positive integer. Then ωs(G+H) =  max{ωs(G) + ωpnds(H), ωs(H) + ωpnds(G)} if G and H are non-complete max{ωs(G), ωpnds(G) + 1} if G is non-complete and H = Kn. Theorem 6. Let G be a non-trivial connected graph and let H be any graph. Then C ⊆ V (G ◦ H) is a superclique in G ◦ H if and only if one of the following statements holds: (i) C is a clique in G. (ii) C is a superclique in Hv for some v ∈ V (G). (iii) C = Cv ∪ {v} for some v ∈ V (G) and superclique Cv in Hv. Proof. Suppose C is a superclique in G ◦H. If C ⊆ V (G), then C is a clique in G. So suppose that C ∩ V (Hv) ̸= ∅ for some v ∈ V (G). Then C is a clique in v +Hv. Suppose first that C ⊆ V (Hv) and let x, y ∈ C where x ̸= y. Since C is a superclique in G ◦ H, there exists z ∈ V (G◦H)\C such that z ∈ NG◦H(x)\NG◦H(y) or z ∈ NG◦H(y)\NG◦H(x). Since v ∈ NG◦H(x) ∩ NG◦H(y), z ̸= v. Hence, z ∈ V (Hv) \ C and z ∈ NHv(x) \ NHv(y) R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1225 or z ∈ NHv(y) \ NHv(x). This shows that C is a superclique in Hv. Next, suppose that v ∈ C. Then C = {v} ∪ Cv where Cv = C ∩ V (Hv). It is routine to show that Cv is a superclique in Hv. For the converse, suppose first that C is a clique in G. Let a, b ∈ C where a ̸= b. Pick any c ∈ V (Ha). Then c ∈ V (G ◦ H) \ C and c ∈∈ NG◦H(a) \ NG◦H(b). Thus, C is a superclique in G ◦ H. Next, suppose that C is a superclique in Hv for some v ∈ V (G). Then clearly, C is a superclique in G ◦H. Finally, suppose that C = Cv ∪ {v} for some v ∈ V (G) and superclique Cv in Hv. Let p, q ∈ C where p ̸= q. If p, q ∈ Cv, then there exists t ∈ V (Hv) \ Cv such that t ∈ NHv(p) \NHv(q) or t ∈ NHv(q) \NHv(p) because Cv is a superclique in Hv. It follows that t ∈ V (G ◦H) \ C and t ∈ NG◦H(p) \ NG◦H(q) or t ∈ NG◦H(q) \ NG◦H(p). Suppose p = v. Choose any w ∈ NG(v). Then w ∈ NG◦H(p) \ NG◦H(q). This proves that C is a superclique in G ◦H. The next result is a consequence of Theorem 6. Corollary 7. Let G be a non-trivial connected graph and let H be any graph. Then ωs(G ◦H) = max{ω(G), ωs(H) + 1}. Gaquing and Canoy in [8] obtained the next result. Theorem 7. Let G and H be any connected non-trivial graphs. Then C = ⋃ x∈S [{x}×Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a clique in G[H] if and only if S a clique in G and Tx is a clique in H for each x ∈ S. In particular, ω(G[H]) = ω(G)ω(H). Theorem 8. Let G and H be any connected non-trivial graphs. Then C = ⋃ x∈S [{x}×Tx], where S ⊆ V (G) and Tx ⊆ V (H) for each x ∈ S, is a superclique in G[H] if and only if S a superclique in G and Tx is a superclique in H for each x ∈ S. Proof. Suppose C is a superclique in G[H]. Then S and each Tx are cliques in G and H, respectively, by Theorem 7. Let x, y ∈ S with x ̸= y. Choose any a ∈ Tx and b ∈ Ty. Then (x, a), (y, b) ∈ C. Since C is a superclique in G[H], there exists (z, c) ∈ V (G[H]) \C such that (z, c) ∈ NG[H]((x, a)) \ NG[H]((y, b)) or (z, c) ∈ NG[H]((y, b)) \ NG[H]((x, a)). Since {x}× (V (H) \ Tx) ⊆ NG[H]((y, b)) and {y}× (V (H) \ Ty) ⊆ NG[H]((x, b)), it follows that z /∈ {x, y} and z ∈ V (G) \ S. Hence, z ∈ NG(x) \ NG(y) or z ∈ NG(y) \ NG(x), showing that S is a superclique in G. Next, let x ∈ S and let p, q ∈ Tx with p ̸= q. Then (x, p), (x, q) ∈ C. Since C is a superclique in G[H], there exists (w, t) ∈ V (G[H]) \ C such that (w, t) ∈ NG[H]((x, p)) \ NG[H]((x, q)) or (w, t) ∈ NG[H]((x, q)) \ NG[H]((x, p)). This would imply that w = x, t ∈ V (H)\Tx, and t ∈ NH(p)\NH(q) or t ∈ NH(q)\NH(p). Therefore, Tx is a superclique in H. For the converse, suppose that S a superclique in G and Tx is a superclique in H for each x ∈ S. By Theorem 7, C is a clique in G[H]. Let (v, a), (w, b) ∈ C with (v, a) ̸= (w, b) and consider the following cases: R. Dela Cerna, S. Canoy, Jr. / Eur. J. Pure Appl. Math, 15 (3) (2022), 1217-1228 1226 Case 1. v = w. Then a, b ∈ Tv and a ̸= b. Since Tv is a superclique in H, there exists d ∈ V (H) \ Tv such that d ∈ NH(a) \NH(b) or d ∈ NH(b) \NH(a). It follows that (v, d) ∈ V (G[H]) \ C and (v, d) ∈ NG[H]((v, a)) \NG[H]((v, b)) or (v, d) ∈ NG[H]((v, b)) \NG[H]((v, a)). Case 2. v ̸= w. Since v, w ∈ S and S is a superclique in G, there exists u ∈ V (G)\S such that u ∈ NG(v)\ NG(w) or u ∈ NG(w) \ NG(v). Then (u, a) ∈ V (G[H]) \ C and (u, a) ∈ NG[H]((v, a)) \ NG[H]((v, b)) or (u, a) ∈ NG[H]((v, b)) \NG[H]((v, a)). Accordingly, C is a superclique in G[H]. Corollary 8. Let G and H be any connected non-trivial graphs. Then ωs(G[H]) = ωs(G)ωs(H). Proof. Let S and D be ωs-sets in G and H, respectively. Then C0 = S × D is a superclique in G[H] by Theorem 8. It follows that ωs(G[H]) ≥ |C0| = |S||D| = ωs(G)ωs(H). Now, let C be an ωs-set in G[H]. Then C = ⋃ x∈S [{x} × Tx] and S and each Tx are supercliques in G and H, respectively, by Theorem 8. Hence, ωs(G[H]) = |C| = ∑ x∈S |Tx| ≤ ωs(G)ωs(H). This establishes the desired equality. The next result is also obtained from [8]. Theorem 9. Let G and H be any connected graphs. Then C is a clique in G□H if and only if C = S × {a} for some a ∈ V (H) and clique S in G or C = {x} × R for some x ∈ V (G) and clique R in H. In particular, ω(G□H) = max{ω(G), ω(H)}. Theorem 10. Let G and H be any connected non-trivial graphs. Then C is a superclique in G□H if and only if C = S×{a} for some a ∈ V (H) and clique S in G or C = {x}×R for some x ∈ V (G) and clique R in H. Proof. Suppose C is a superclique in G[H]. Since C is a clique, C = S × {a} for some a ∈ V (H) and clique S in G or C = {x} × R for some x ∈ V (G) and clique R in H by Theorem 9. For the converse, suppose that C = S × {a} for some a ∈ V (H) and clique S in G. Then C is a clique in G□H by Theorem 9. Let (v, a), (w, a) ∈ C such that v ̸= w. Choose REFERENCES 1227 any b ∈ NH(a). Then (v, b) ∈ V (G□H) \ C and (v, b) ∈ NG□H((v, a)) \ NG□H((w, a)). Next, suppose that C = {x} × R for some x ∈ V (G) and clique R in H. Again, C is a clique in G□H by Theorem 9. Let (x, p), (x, q) ∈ C with p ̸= q. Choose any y ∈ NG(x). Then (y, p) ∈ V (G□H) \ C and (y, p) ∈ NG□H((x, p)) \NG□H((x, q)). In either case, we find that C is a superclique in G□H. The next result follows from Theorem 9 and Theorem 10. Corollary 9. Let G and H be non-trivial connected graphs. Then ωs(G□H) = ω(G□H) = max{ω(G), ω(H)}. 4. Conclusion Any graph admits a superclique and the superclique number of a graph does not exceed the clique number of the graph. It is shown that the difference of the clique number and superclique number can be made arbitrarily large. Supercliques in the join, corona, lexicographic product, and Cartesian product of two graphs have been characterized. From these characterizations, respective superclique numbers have been determined. This new invariant can also be studied for graphs under other binary operations. Moreover, it may be possible that the invariant has relationship with other graph-theoretic parameters apart from the ones involving the strong metric dimension. Acknowledgements The authors would like to thank the referees for the suggestions and comments that helped improve the paper. Also, the authors would like to extend their thankfulness to the Department of Science and Technology - Accelerated Science and Technology Human Re- source Development Program (DOST-ASTHRDP)-Philippines, and MSU-Iligan Institute of Technology for funding this research. References [1] P. Acal and H. Rara. The strong connected metric dimension in the join and corona of graphs. Advances and Applications in Discrete Mathematics, 21(1):91–101, 2019. [2] R. Brigham, G. Chartrand, R. Dutton, and P. Zhang. Resolving domination in graphs. Mathematica Bohemica, 128(1):25–36, 2003. [3] G. Cagaanan and S. Canoy Jr. On the geodetic covers and geodetic bases of the composition g[km]. Ars Combinatoria, 79:33–45, 2006. [4] G. Chartrand, L. Eroh, M. Johnson, and O.R. Oellermann. Resolvability in graphs and the metric dimension of a graph the metric dimension of a graph. Discrete Applied Mathematics, 105:99–113, 2000. REFERENCES 1228 [5] M.B. Cozzens and L.L. Kelleher. Dominating cliques in graphs. Discrete Mathematics, 86:101–116, 1990. [6] T.V. Daniel and S. Canoy Jr. Clique domination in a graph. Applied Mathematical Sciences, 9(116):5749–5755, 2015. [7] R. Eballe and S. Canoy Jr. Steiner sets in the join and composition of graphs. Congresus Numerantium, 170:65–73, 2004. [8] N. Gaquing and S. Canoy Jr. On cliques and forcing m-convexity numbers of graphs. Ars Combinatoria, 103:321–331, 2012. [9] M.R. Garey and D.S. Johnson. Computers and intractability: A guide to the theory of np completeness. Freeman, New York, 1979. [10] F. Harary and R.A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2:191–195, 1976. [11] R. Hinampas and S. Canoy Jr. 1-movable domination in graphs. Applied Mathematical Sciences, 8(172):8565–8571, 2014. [12] R. Luce and A. Perry. A method of matrix analysis of group structure. Psychometrika, 14:95–116, 1949. [13] G. Monsanto, P. Acal, and H. Rara. On strong resolving domination in the join and corona of graphs. European Journal of Pure and Applied Mathematics, 13(1):170–179, 2020. [14] J.W. Moon and L. Moser. On clique in graphs. Israel J. Math., 9:23–28, 1965. [15] O.R. Oellermann and J. Peters-Fransen. Metric dimension of cartesian products of graphs. Utilitas Math., 69:33–41, 2006. [16] O.R. Oellermann and J. Peters-Fransen. The strong metric dimension of graphs and digraphs. Discrete Applied Mathematics, 155:356–364, 2007. [17] F. Roberts and J. Spencer. A characterization of clique graphs. Journal of Combi- natorial Theory, 10:102–108, 1971. [18] A. Sebo and E. Tannier. On metric generators of graphs. Math. Oper. Res., 29:383– 393, 2004. [19] P.J. Slater. Dominating and reference sets in graphs. J. Math. Phys. Sci., 22:445–455, 1988. [20] H. Sumaoy and H. Rara. On restrained and movable strong resolving domination in graphs. European Journal of Pure and Applied Mathematics, 14(4):1367–1378, 2021.