EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 4, 2024, 2930-2938 ISSN 1307-5543 – ejpam.com Published by New York Business Global Convex Accessibility Number of the Complements and Some Binary Operations of Graphs Harold B. Samson1,∗, Imelda S. Aniversario2, Mary Joy F. Luga3 1 Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines 2 Department of Mathematics and Statistics, College of Science and Mathematics, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City , Philippines 3 Integrated Developmental School, College of Education, Mindanao State University-Iligan Institute of Technology, 9200 Iligan City, Philippines Abstract. This study explores various aspects of the Convex Accessibility Number in graph the- ory, focusing on some binary operations namely Cartesian Product and Strong Product and Com- plements of graphs. The computation of the Convex Accessibility Number of Cartesian Product and Strong Product of graphs is examined. Also, the Convex Accessibility Number of the Com- plement of some known graphs is explored. Through these investigations, this study contributes to a deeper understanding of the Convex Accessibility Number in graph theory, offering insights into its behavior under different graph operations and Complementation scenarios. 2020 Mathematics Subject Classifications: 05C12 Key Words and Phrases: H-Convex Accessibility Number, Convex Subgraph, Strong Product, Cartesian Product, Complement of a Graph, Accessibility Number 1. Introduction The concept of H-Convex accessibility number was introduced by R. G. Artes, Jr. and M.J. F. Luga [3] [2] in 2014, it was about the H-Convex accessibility number of some graphs and graphs under binary operations join, corona and composition. This paper presents the H-convex accessibility number for various graph operations such as Cartesian products, strong products, and complements was determined by ana- lyzing how the proper convex subgraphs influence the accessibility number. As the size of these proper convex subgraphs increases, the Convex Accessibility Number tends to approach 1. Therefore, by starting with smaller convex subgraphs and progressively ex- panding their size, the study aimed to derive a general formula by comparing the Convex Accessibility Numbers across different graph configurations. The distance from a vertex ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i4.5332 Email addresses: harold.samson@g.msuiit.edu.ph (H. Samson), imelda.aniverario@g.msuiit.edu.ph (I. Aniversario), maryjoy.luga@g.msuiit.edu.ph (M.J. Luga) https://www.ejpam.com 2930 Copyright: © 2024 The Author(s). (CC BY-NC 4.0) H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2931 u to a subgraph H is defined as the shortest path between u and any vertex v ∈ H. In this paper, the subgraph H is required to be a proper convex subgraph of a graph G. The accessibility number is defined as the minimum k for which G is H-convex k- accessible. The Convex Accessibility Number of a graph helps in covering all points with the mini- mum number of surveillance cameras, which is essential for secure network design. It also aids in placing key facilities like hospitals or fire stations to improve emergency response times. In wireless sensor networks, it determines the optimal sensor placement for full coverage, ensuring efficient resource use. All the graphs considered in this study are finite, undirected and connected. Most of the definitions are from [1]. Those that are not from the said source are so indicated. The symbols V (G) and E(G) denote the vertex set and edge set of G. An edge joining vertices u, v ∈ G is denoted by [u, v]. In this case, u and v are adjacent. A graph H is a subgraph of a graph G, denoted by H ⪯ G, if V (H) ⊆ V (G) and E(H) ⊆ E(G). A graph H = ⟨V (H)⟩ is an induced subgraph of a graph G if H ⪯ G and two vertices in H are adjacent whenever they are adjacent in G. A graph H is a proper subgraph of G if E(G) \ E(H) ̸= ∅. Given a connected graph G, the distance between two vertices u and v in G, denoted by dG(u, v) is the length of the shortest path joining u and v[1]. The distance between a vertex u ∈ V (G) and a subgraph H of G is defined as dG(u,H) = min {dG(u, v) : v ∈ V (H)}. For vertices u and v of a graph G, a u-v geodesic is any shortest path in G joining u and v. The closed interval IG[u, v] is the set of vertices lying in any u-v geodesics of G and the set IG[u, v] consist all the vertices in any u-v geodesic including u and v. A subset C of V (G) is convex if for every u, v ∈ C, the vertex set of every u-v geodesic is contained in C. Equivalently, C is convex if for every u, v ∈ C, the closed interval IG[u, v] is a subset of C. A convex subgraph H of a graph G is a subgraph of G induced by a convex subset of V (G). A proper convex subgraph H of G. Subgraph H is said to be the maximum proper convex subgraph of G if for any proper convex subgraph H∗ with H ⪯ H∗ ⪯ G, then H = H∗. A graph G is H-convex k-accessible if there exists a proper convex subgraph H of G such that for every v ∈ V (G) \ V (H), there exists u ∈ V (H) satisfying dG(u, v) ≤ k, k ∈ N. For a proper convex subgraph H of G, we define the H-Convex accessbility number of G as ΓH(G) = min{k : G is H convex k accessible}. The complement of a graph G is a graph Ḡ, with vertex set same as G and two vertices in Ḡ are adjacent if and only if they are not adjacent in G. The Cartesian Product G□H of graphs G and H is a graph such that the vertex set G□H is the cartesian product V (G) × V (H) and vertices (u, v) and (u′, v′) are adjacent in G□H if and only if u is adjacent to u′ in G or, v is adjacent to v′ in H. The Strong product G ⊠H of graphs G and H is a graph such that the vertex set of G⊠H is the cartesian product V (G)×V (H) and distinct vertices (u, u′) and (v, v′) are adjacent in G⊠H if and only if u = v and u′ is adjacent to v′ in H or, u′ = v′ and uis adjacent to v in G or, u is adjacent to v in G and u′ is adjacent to v′ in H. For a set C ⊂ V (G ×H), we denote, CG = {u : (u, v) ∈ C for some v ∈ V (H)} and CH = {v : (u, v) ∈ C for some u ∈ V (G)}. A set C ∈ V (G□H) is a convex set in G□H if and only if C = CG□CH , where CG and CH are convex sets in G and H respectively, H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2932 where G and H are connected graphs [5]. The distance between vertices (g, h) and (g′, h′) in the Cartesian product G□H is equal to dG□H((g, h), (g′, h′)) = dG(g, g ′) + dH(h, h′) [4]. The distance between ver- tices (u, v) and (u′, v′) in the Strong product G ⊠ H is equal to dG⊠H((u, v), (u′, v′)) = max{dG(u, u′), dH(v, v′)} [4]. 2. H Convex accessibility Number of the Complement of Some Known Graphs In this section, we established the H-Convex accessibility number of the complement of some known graphs. Theorem 1. Let G be a graph such that G = Pn = [x1, x2, . . . , xn] for n ≥ 4 and H be a proper convex subgraph of G. Then ΓH(G) = { 2, if H = K1 or H = P2 = [xi, xi+2] 1, otherwise. Proof. Let G = Pn be a connected path graph where the vertices are x1, x2, x3, . . . , xn and the edges are [x1, x2][x2, x3], [x3, x4], . . . , [xn−1, xn] ∈ E(G). Consider the following cases for the graph G and its complement G. Case 1: H = K1. Let H = K1 where V (H) = {xi} and xi is not an end vertex of G. This means that xi is connected to xi−1 and xi+1 in G. Consequently, in the complement G, xi is adjacent to all vertices except xi−1 and xi+1. Therefore, the distance from xi to any vertex u ∈ V (G) \ {xi−1, xi+1} is 1. For xi−1 and xi+1, the distance is 2. Thus, dG(u, xi) ≤ 2 for all u ∈ V (G) \ {xi}. Hence, G is K1-convex 2-accessible, i.e., ΓK1(G) = 2. Case 2: H = P2. Let H = P2 in G. Without loss of generality, assume that V (H) = {xi, xi+2}. Since [xi, xi+2] ∈ E(G), the distance dG(u, P2) = 1 if and only if u ̸= xi−1 and u ̸= xi+1. However, dG(xi−1, P2) = 2 and dG(xi+1, P2) = 2. Therefore, for any u ∈ V (G) \ V (P2), dG(u, P2) ≤ 2. Therefore, G is P2-convex 2-accessible, i.e.,ΓP2(G) = 2. Case 3: The degree of x1 and xn in G are both 1. In this case, x1 and xn are the start and end vertices of the path G, respectively, meaning they are not directly connected in G. Therefore, there exists and edge [x1, xn] ∈ E(G) connecting x1 and xn. Considering this path as the proper convex subgraph in G, G is P2-convex 1-accessible, i.e., ΓP2(G) = 1. ■ Consider the Complement of P5, that is P5. If H1 = K1, then ΓH1(P5) = 2. If H2 = [a, c], then ΓH2(P5) = 2. If H3 = [a, e], then ΓH3(P5) = 1. If H4 = {a, c, e}, then ΓH4(P5) = 1. H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2933 Figure 1: P5 Theorem 2. Let G be a graph such that G = Cn for n ≥ 5 and H be a proper convex subgraph of G. Then ΓH(G) = { 2, if H = P2 or H = K1 1, otherwise. Proof. Let Cn be a cycle graph defined by the sequence of vertices [u1, u2, . . . , un, u1] where the edges are [u1, u2], [u2, u3], . . . , [un−1, un], [un, u1] ∈ E(Cn). In this cycle graph, observe that [ui−1, ui] and [ui, ui+1] are edges of Cn. This implies that [ui−1, ui] and [ui, ui+1] cannot be edges in the complement graph Cn. Without loss of generality, let P2 = {ui, ui+2} where [ui, ui+2] ∈ ECn . For any vertex v in Cn, the distance dCn (v, P2) is defined as the minimum distance from v to either ui or ui−2. This means that for v = ui−1 or v = ui+1, dCn (v, P2) = 2 and for any other vertex v, which is neither v = ui−1 nor v = ui+1, dCn (v, P2) = 2 as well. Thus, the distance from any vertex to P2 is atmost 2, showing that Cn is P2-convex 2-accessible. ■ Remark 1. For the star, wheel, fan, complete graph, complete bipartite and join, the complement of these graphs have isolated vertices. This means that it is not possible to get the H convex accessibility number of these graphs. 3. H convex Accessibility Number of the Cartesian Product of Graphs In this section, we established the H-Convex accessibility number of the Cartesian product of graphs. Theorem 3. Let G1 and G2 be connected graphs and H = H1□H2 be a proper convex subgraph of V (G1□G2), where H1 and H2 are proper convex subgraphs of G1 and G2 respectively. Then, ΓH(G1□G2) = ΓH1(G1) + ΓH2(G2) Proof. Suppose that G1 and G2 are connected graphs and H = H1□H2 is a convex set in G1□G2. By [5], H1 and H2 are convex sets in G1 and G2 respectively. H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2934 Consider any vertex (u, v) ∈ V (G1□G2) \ V (H1□H2) and any vertex (x, y) ∈ V (H1□H2). Then the distance between these vertices in G1□G2 is given by, dG1□G2((u, v), (x, y)) = dG1(u, x) + dG2(v, y). Since H1 is a proper convex subgraph of G1 and H2 is also a proper convex subgraph of G2, we have ΓH1(G1) ≤ dG1(u,H1) ΓH2(G2) ≤ dG2(v,H2). Adding these inequalities, we have ΓH1(G1) + ΓH2(G2) ≤ dG1(u,H1) + dG2(v,H2) ΓH1(G1) + ΓH2(G2) ≤ dG1□G2((u, v),H1□H2). Since (u, v) and (x, y) are arbitrarily chosen vertices in G1□G2 and H1□H2, respectively, the distance dG1□G2 = ((u, v), (x, y)) represents the shortest path distance between (u, v) and (x, y). Therefore, dG1□G2((u, v),H1□H2) = ΓH(G1□G2). Substituting this result, we have ΓH1(G1) + ΓH2(G2) ≤ ΓH(G1□G2). By the definition of convex accessibility number, we also have ΓH(G1□G2) ≤ ΓH1(G1) + ΓH2(G2). Combining these inequalities, we obtain, ΓH(G1□G2) = ΓH1(G1) + ΓH2(G2). ■ Consider the Cartesian Product of P6 and P6, that is P6□P6 is as shown in Figure 2 and a proper convex subgraph H = P2□P2, where P2 is a convex subgraph of P6. For this graph, ΓH(P6□P6) = ΓP2(P6) + ΓP2(P6) = 2 + 2 = 4. 4. H-convex Accessibility Number of the Strong Product of Graphs In this section, we established the H-Convex accessibility number of the Strong product of graphs. H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2935 Figure 2: The Cartesian Product of P6 and P6 Theorem 4. Let G and H be connected graphs. If C = CG⊠CH , then a set C ⊂ V (G⊠H) is a convex set in G⊠H, where CG and CH are convex sets in G and H respectively. Proof. Let G and H be a connected graph and let C = CG ⊠ CH , where CG ⊂ V (G) and CH ⊂ V (H). We aim to show that C is convex in G⊠H. Consider any two vertices (u, v), (u′, v′) ∈ C. Let (x, y) be a vertex on a (u, v) - (u′, v′) geodesic in G⊠H. Then, by definition of strong product, one of the following must hold, u = x and v is adjacent to y in H, or, v = y and u is adjacent to x in G or u is adjacent to x in G and v is adjacent to y in H. Case 1: u = x and v is adjacent to y in H. Suppose that u = x and v is adjacent to y in H. By assumption, there exist the u-u′ path joining vertices u and u′ in G. Hence, u = x must be in CG. Similarly, y is also contained in CH because CH is convex. Case 2: v = y and u is adjacent to x in G. Assume that v = y and u is adjacent to x in G. Then, x must be in CG because CG is convex. Analogously, there exist a v-v′ path joining vertices v and v′ in H. Thus, y = v is in CH . Case 3: u is adjacent to x in G and v is adjacent to y in H. Let u is adjacent to x in G and v is adjacent to y in H. This must mean that x is contained in CG since CG is convex. In a similar fashion, y is also contained in CH since CH is convex. In all cases, (x, y) is contained in C = CG ⊠ CH . Therefore, C is convex in G⊠H. ■ Theorem 5. Let G and H be connected graphs. If a set C ⊂ V (G⊠H) is a convex set in G⊠H, then C = CG ⊠ CH , where CG and CH are convex sets in G and H respectively. Proof. Suppose a set C ∈ V (G ⊠ H) is a convex set in G ⊠ H. Let (u, u′) ∈ CG and x be a vertex in a u - u′ geodesic in G. By definition of strong product, there exists (v, v′) ∈ CH such that the either u = x and v is adjacent to v′ in H, oru is adjacent to x in G and v is adjacent to v′ in H. In either cases, (x, v) and (x, v′) ∈ C. Hence, x ∈ CG Thus. CG is convex in G. Similarly, let a, a′ ∈ CH and y be a vertex set in a a-a′ geodesic in H. By definition of strong product, there exist (b, b′) ∈ CG such that a = y and b is H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2936 adjacent to b′ in G, or b is adjacent to b′ in G and a is adjacent to y in H. In both cases, (b, y) and (b′, y) ∈ C. Thus, y ∈ CH and CH is convex in H. The assumption implies that C ⊆ CG ⊠ CH . Assume that (i, j) ∈ CG ⊠ CH . Then, there exists m ∈ V (G) and n ∈ V (H) such that either i = m and j is adjacent to n in H, or, j = n and i is adjacent to m in G, or i is adjacent to m in G and j is adjacent to n in H. Note that C is convex, it follows that (i, j) ∈ C.Thus, CG ⊠ CH ⊆ C. Consequently, C = CG ⊠ CH . ■ Corollary 1. Let G and H be connected graphs. A set C ∈ V (G ⊠ H) is a convex set in G ⊠ H if and only if C = CG ⊠ CH , where CG and CH are convex sets in G and H respectively. Proof. Notice that the preceding two theorems have established both the sufficiency and necessity conditions required for this corollary. Thus, this directly follows from The- orem 4 and Theorem 5. Theorem 6. Let G1 and G2 be connected graphs and H = H1 ⊠H2 be a proper convex subgraph of V (G1 ⊠ G2), where H1 and H2 are proper convex subgraphs of G1 and G2 respectively. Then, ΓH(G1 ⊠G2) = max{ΓH1(G1),ΓH2(G2)} Proof. Let G1 and G2 be connected graphs and H = H1 ⊠ H2 be a proper convex subgraph of G1 and G2. We aim to show that the graph G1⊠G2 has a certain relationship with the convexity parameters of G1 and G2. Consider an arbitrary vertex (u, v) ∈ V (G1 ⊠G2) \ V (H). Without loss of generality, let (u′, v′) ∈ V (H). According to [4], the distance in the strong product graph G1 ⊠G2 is given by, dG1⊠G2((u, v), (u ′, v′)) = max {dG1(u, u ′), dG2(v, v ′)}. By [3], we know that, ΓH1(G1) ≤ dG1(u, u ′) and ΓH2(G2) ≤ dG2(v, v ′). Thus, we have max {ΓH1(G1),ΓH2(G2)} ≤ max {dG1(u, u ′), dG2(v, v ′)}. This simplifies to max {ΓH1(G1),ΓH2(G2)} ≤ dG1⊠G2((u, v), (u ′, v′)). Since (u, v) and (u′, v′) are arbitrarily chosen vertices, the distance dG1⊠G2((u, v), (u ′, v′)) represents the shortest path between these vertices. Therefore dG1⊠G2((u, v), (u ′, v′)) = ΓH(G1 ⊠G2). Substituting this to our inequality we get max{ΓH1(G1),ΓH2(G2)} ≤ ΓH(G1 ⊠G2). H. B. Samson, I. S. Aniversario, M. J. F. Luga / Eur. J. Pure Appl. Math, 17 (4) (2024), 2930-2938 2937 From [3], we also have, ΓH(G1 ⊠G2) ≤ max{ΓH1(G1),ΓH2(G2)}. Combining these results, we conclude ΓH(G1 ⊠G2) = max{ΓH1(G1),ΓH2(G2)}.■ Consider the Strong Product of P8 and P6, that is P8⊠P6 is as shown in Figure 3 and a proper convex subgraph H = P2 ⊠ P2, where P2 is a convex subgraph of P8 and P2 is a proper convex subgraph of P6. For this graph, ΓH(P8 ⊠ P6) = max {ΓP2(P8),ΓP2(P6)} = max{3, 2} = 3. Figure 3: The Strong Product of P8 and P6 Conclusion This study has advanced the understanding of the Convex accessibility number by investigating its behavior under various graph operations and complementation. The analysis of the Cartesian and Strong products revealed distinct patterns in the Convex accessibility number, offering valuable insights into how these binary operations impact graph properties. Additionally, exploring the Convex accessibility number of graph com- plements has provided further clarity on its interaction with graph structures. These findings not only enhance theoretical knowledge but also pave the way for future research in graph theory, particularly in understanding how different operations affect Convex ac- cessibility. By bridging gaps in the existing literature and presenting new perspectives, this study contributes significantly to the broader field of graph theory and its applications. Acknowledgements The authors are grateful to the Department of Science and Technology - Accelerated Science and Technology Human Resource Development Program (DOST-ASTHRDP)- Philippines and MSU-Iligan Institute of Technology for funding this research. REFERENCES 2938 References [1] F Harary. Graph Theory. Addison-Weasley Publishing Company, Boston, USA, 1969. [2] Jr R Artes and MJ Luga. Convex Accessibility in Graph Operation. Hikari Ltd, 8(116):5763–5770, 2014. [3] Jr R Artes and MJ Luga. Convex Accessibility in Graphs. Hikari Ltd, 8(88):4361–4366, 2014. [4] W Imrich R Hammack and S Klavzar. Handbook on Product Graphs. Taylor and Francis Group, England, United Kingdom, 2011. [5] Jr S Canoy and IJL Garces. Convex Under Some Graph Operations. Graphs and Combinatorics, 18:787–793, 2002.