EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 17, No. 2, 2024, 922-930 ISSN 1307-5543 – ejpam.com Published by New York Business Global J-Open Independent Sets in Graphs Javier A. Hassan1,∗, Nuruddina M. Bakar1, Norwajir S. Dagsaan1, Mercedita A. Langamin1, Nurijam Hanna M. Mohammad1, Sisteta U. Kamdon1 1 Mathematics and Sciences Department, College of Arts and Sciences, MSU-Tawi-Tawi College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines Abstract. Let G be a graph with vertex and edge-sets V (G) and E(G), respectively. Then O ⊆ V (G) is called a J-open independent set of G if O is a singleton set or O is an independent set of G and for every a, b ∈ V (G), NG(a)\NG(b) ̸= ∅ and NG(b)\NG(a) ̸= ∅. The maximum cardinality of a J-open independent set of G, denoted by αJ(G), is called the J-open independence number of G. In this paper, we introduce this parameter and we show that it is always less than or equal to the standard independence (resp. J-total domination) parameter of a graph. In fact, their differences can be made arbitrarily large. In addition, we show that J-open independence parameter is incomparable with hop independence parameter. Moreover, we derive some formulas and bounds of the parameter for some classes of graphs and the join of two graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: J-open set, J-open independent set, J-open independence number 1. Introduction An independent set in a graph is a subset of a vertex-set of a graph where each pair of distinct vertices are not of distance one. In other words, it is a set of vertices that are not connected by an edge. This concept is fundamental in graph theory and has a wide range of applications in various field. Some studies on independent sets in graphs can be found in [2–4, 12, 17, 18]. In 2022, hop independent set in a graph and its parameter was introduced by Hassan et al. [8]. They defined a set S ⊆ V (G) is a hop independet set of G if any two distinct vertices in S are not at a distance two from each other, that is, dG(u,w) ̸= 2 for any distinct vertices u,w ∈ S. The maximum cardinality of a hop independent set of G, ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5084 Email addresses: javierhassan@msutawi-tawi.edu.ph (J. A. Hassan), nuruddinabakar@msutawi-tawi.edu.ph (N. M. Bakar), norwajirdagsaan@msutawi-tawi.edu.ph (N. S. Dagsaan), merceditalangamin@msutawi-tawi.edu.ph (M. A. Langamin), hannamohammad@msu-tawi-tawi.edu.ph (H. M. Mohammad), sistetakamdon@msu-tawi-tawi.edu.ph (S. U. Kamdon) https://www.ejpam.com 922 © 2024 EJPAM All rights reserved. J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 922-930 923 denoted by αh(G), is called the hop independence number of G. They have shown that any maximum hop independent set S of G is always a hop dominating, that is, the hop independence number of a graph is always greater than or equal to the hop domination parameter. Moreover, they derived some bounds and formulas for some special graphs and graphs under some binary operations. Some studies on variants of hop independent sets and other hop-related concepts can be found in [1, 5–7, 9, 11, 13–16] In this paper, we introduce new independence parameter called J-open independence. We investigate this concept on some families of graphs and on the join of two graphs. We believe, the results of this study could led to other interesting research directions in the future. 2. Terminology and Notation Let G = (V (G), E(G)) be a simple and undirected graph. The distance dG(u, v) in G of two vertices u, v is the length of a shortest u-v path in G. The greatest distance between any two vertices in G, denoted by diam(G), is called the diameter of G. Two vertices x, y of G are adjacent, or neighbors, if xy is an edge of G. The open neighborhood of x in G is the set NG(x) = {y ∈ V (G) : xy ∈ E(G)}. The closed neighborhood of x inG is the setNG[x] = NG(x)∪{x}. IfX ⊆ V (G), the open neighborhood of X in G is the set NG(X) = ⋃ x∈X NG(x). The closed neighborhood of X in G is the set NG[X] = NG(X) ∪X. A subset D = {d1, d2, · · · , dm} of vertices of G is called a J-open set if NG(di) \NG(dj) ̸= ∅ for every i ̸= j, where i, j ∈ {1, 2, . . . ,m}. A J-open set is called a J-total dominating set of G if D = {d1, d2, . . . , dm} is a total dominating set of G. The J-total domination number of G, denoted by γJt(G), is the maximum cardinality of a J-total dominating set of G [10]. A path graph is a non-empty graph with vertex-set {x1, x2, . . . , xn} and edge-set {x1x2, x2x3, . . . , xn−1xn}, where the x ′ is are all distinct. The path of order n is denoted by Pn. If G is a graph and u and v are vertices of G, then a path from vertex u to vertex v is sometimes called a u-v path. The cycle graph Cn is the graph of order n ≥ 3 with vertex-set {x1, x2, . . . , xn} and edge-set {x1x2, x2x3, . . . , xn−1xn, xnx1}. Let G and H be any two 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)}. A subset S of V (G) is called a independent if for every pair of distinct vertices x, y ∈ S, dG(x, y) ̸= 1. The maximum cardinality of a independent set in G, denoted by α(G), is called the independence number of G. Any independent set S with cardinality equal to α(G) is called an α-set of G. A subset S of V (G) is called a hop independent set of G if any two distinct vertices in S are not at distance two from each other, that is, dG(v, w) ̸= 2 for any two distinct J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 922-930 924 vertices v, w ∈ S. The hop independence number of G, denoted by αh(G), is the maximum cardinality of a hop independent set of G [8]. 3. Results We begin this section by introducing the concept of J-open independence in graphs. Definition 1. Let G be a graph with vertex and edge-sets V (G) and E(G), respectively. Then O ⊆ V (G) is called a J-open independent set of G if O is a singleton set or O is an independent set of G and for every a, b ∈ V (G), NG(a)\NG(b) ̸= ∅ and NG(b)\NG(a) ̸= ∅. The maximum cardinality of a J-open independent set of G, denoted by αJ(G), is called the J-open independence number of G. Example 1. Consider the graph G = P4 in Figure 1 below. Let O = {a, d}. Then dG(a, d) = 3. Thus, O is an independent set of G. Observe that NG(a) = {b} and NG(d) = {c}. Hence, NG(a)\NG(d) = {b}\{c} = {b}, andNG(d)\NG(a) = {c}\{b} = {c}. Therefore, O is a J-open independent set of G. Moreover, it can be verified that αJ(G) = 2. a b c d P4 : Figure 1: Graph G = P4 with αJ (P4) = 2 Remark 1. Let G be a graph. Then each of the following holds: (i) A J-open set O of G may not be an independent set of G. (ii) An independent set of G may not be a J-open set of G. The remark above says that the definition of a J-open independence makes sense. 4. Relationships of J-Open Independence and Independence Parameters Theorem 1. Let G be a graph. Then (i) αJ(G) ≤ α(G); and (ii) 1 ≤ αJ(G) ≤ |V (G)| − 1. Proof. (i) Let G be a graph and let O be a maximum J-open independent set of G. Then O is an independent set of G and αJ(G)=|O|. Since α(G) is the maximum cardi- nality among all independent sets in G, if follows that α(G) ≥ |O|=αJ(G). (ii) Let G be a graph and let V (G) = {a1, a2, ..., an}. Then {a1} is a J-open indepen- dent set of G. Thus, αJ(G) ≥ |{a1}|=1. To show that αJ(G) ≤ |V (G)| − 1. Suppose that J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 922-930 925 G is connected. Let ai, aj ∈ V (G) such that dG(ai, aj) = 1 for some i, j ∈ {1, 2, . . . , n}. Then ai and aj cannot be both in an independent set S of G. Hence, if ai ∈ S, then aj /∈ S or if aj ∈ S, then ai /∈ S. Thus, α(G) ≤ |V (G)| − 1. By (i), αJ(G) ≤ |V (G)| − 1. Now, suppose that G is disconnected. Let Q1, ..., Qk, k ≥ 2 be components of G. Since G ̸= Kn, it follows that Qi is non-trivial for each i ∈ {1, ..., k}. Thus, α(Qi) ≤ |V (Qi)|− 1 for each i ∈ {1, ..., k}. Therefore, α(G) = α(Q1) + ...+ α(Qk) = |V (Qi)| − 1 + ...+ |V (Qk)| − 1 = |V (G)| − k ≤ |V (G)| − 1. Consequently, αJ(G) ≤ |V (G)| − 1 by (i). Theorem 2. Let s, t be positive integers such that 1 ≤ s ≤ t. Then there exists a connected graph H such that αJ(H)=s and α(H)=t. In other words, α(H) − αJ(H) can be made arbitrarily large. Proof. Consider the following two cases. Case 1. s = t Consider the graph H below. . . . a1 a2 a3 b2b1 b3 as−1 bs−1 as bs H : Let O = {a1, a2, · · · , as}. Then O is both a maximum J-open independent and maximum independet set of H. Thus, αJ(H) = G = α(H). Case 2: s < t Let q = t− s and consider the graph H ′ below. x1 x3 x2 . . . xs y2 y1 yq ... xs−1 H ′ : Let O1 = {x1, x2, · · · , xs} and O2 = O1 ∪ {y1, y2 · · · , yq} Then O1 and O2 are maxi- mum J-open independent and maximum independent sets of H ′, respectively. Therefore, αJ(H ′) = s and α(H ′) = s+ q = t. Consequently, αJ(H ′) = s < t = α(H ′). J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 922-930 926 5. Relationships of J-Open Independence and J-Total Domination Parameters Proposition 1. Let G be a graph such that G ̸= Kn. Then αJ(G) ≤ γJt(G), and its bound is tight. Proof. Let G be a graph such that G ̸= Kn. and let Q be a maximum J-open inde- pendent set of G. Then Q is a J-open set in G. Since γJt(G) is a maximum cardinality of a J-open set of G, it follows that γJt(G) ≥ |Q| = αJ(G). For the tightness, consider P4. Then αJ(P4) = 2 = γJt(P4). Theorem 3. Let a and b be positive integers such that 1 ≤ a ≤ b. Then there exists a connected graph G such that αJ(G) = a and γJt(G) = b. Proof. Suppose that a = b. Consider the graph G below. . . . v1 v2 v3 v4 u1 u2 u3 u4 ua−2 ua−1 ua va−2 va−1 va G : Let O1 = {u1, u2, . . . , ua} and O2 = {v1, v2, . . . , va}, Then O1 and O2 are maximum J- open independent and maximumu J-total dominating sets of G, respectively. Therefore, αJ(G) = a = γJt(G). Now suppose that a < b. Let q = b − a and consider the graph H below, where {va, r1, r2, . . . , rq} is a clique. . . . v1 v2 v3 v4 u1 u2 u3 u4 ua−2 ua−1 ua va−2 va−1 va H : ... rq r2 r1 Let Q1 = {u1, u2, . . . , ua} and Q2 = {v1, v2, . . . , va, r1, . . . , rq}. Then Q1 and Q2 are maximum J-open independent and maximum J-total dominating sets of H, respectively. Hence, αJ(H) = a and γJt(H) = a+ q = b. J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 922-930 927 6. The Incomparability of J-Open Independence and Hop Independence Parameters Remark 2. The hop independence and J-open independence parameters of a graph are incomparable. To see this, consider the graph K2 + P5 below. x1 x2 x3 x4 x5 y1 y2 K2 + P5 : Let O1 = {x2, x4} and O2 = {x1, x2, y1, y2}. Then O1 and O2 are maximum J-open inde- pendent and maximum hop independent sets of K2 + P5, respectively. Hence, αJ(K2 + P11) = 2 and αh(K2 + P5) = 4. Next, consider the graph C4 + P11 below. x1 x2 x3 x4 x10x9x5 x7x6 x8 x11 y1 y2 y3 y4 C4 + P11 : Let O′ = {y1, y2, x10, x11} and O′′ = {x2, x4, x6, x8, x10}. Then O′ and O′′ are max- imum hop independent and J-open independent sets of C4 + P11 respectively. Thus, αh(C4 + P11) = 4 and αJ(C4 + P11) = 5. 7. J-Open Independence in the Join of Two Graphs Theorem 4. Let G and H be a graphs. A subset O of a vertex-set V (G+H) of G+H is a J-open independent set of G + H if and only if O satisfies one of the following conditions: (i) O is a J-open independent set of G. (ii) O is a J-open independent set of H. REFERENCES 928 Proof. Let O be a J-open independent set of G + H. Then either O ⊆ V (H) or O ⊆ V (G). If O ⊆ V (G), then O is a J-open independent set of G. Thus, (i) holds. If O ⊆ V (H), then O is a J-open indepedent set of H. Hence, (ii) holds. Conversely, suppose that (i) holds. Since V (G) ⊆ V (G+H), O is a J-open independent set of G+H. Assume that(ii) holds. Since V (H) ⊆ V (G+H), it follows that O is a J-open independent set of G+H. Corollary 1. Let G and H be graphs. Then αJ(G+H) = max{αJ(G), αJ(H)}. Proof. Let O be a maximum J-open independent set of G + H. Then by Theorem 4, O is either a J-open independent set of G or H. If O is a J-open independent set of G, then αJ(G + H) = |O| ≤ αJ(G). If O is a J-open independent set of H, then αJ(G+H) = |O| ≤ αJ(H). On the other hand, suppose that O is a maximum J-open independent set of G. Then by Theorem 4, O is a J-open independent set of G+H. Thus, αJ(G) = |O| ≤ αJ(G+H). Similarly, If O is a maximum J-open independent set of H, then O is a J-open independent set of G+H. Hence, αJ(H) = |O| ≤ αJ(G+H). Consequently, αJ(G+H) = max{αJ(G), αJ(H)}. Acknowledgements The authors would like to thank Mindanao State University - Tawi-Tawi College of Technology and Oceanography for funding this research. Also, the authors would like to thank the referees for their invaluable comments and suggestions that led to the improve- ment of the paper. References [1] V. Bilar, M.A. Bonsocan, J. Hassan, and S. Dagondon. Vertex cover hop dominating sets in graphs. Eur. J. Pure Appl. Math., 17(1):93–104, 2024. [2] E. Davies, M. Jenssen, W. Perkins, and B. Roberts. ndependent sets, matchings, and occupancy fractions. J. Lond. Math. Soc., 96:211–220, 2017. REFERENCES 929 [3] Z. Furedi. The number of maximal independent sets in connected graphs, . J. Graph Theory., 11(4):463–470, 2022. [4] J.R. Griggs, C.M. Grinstead, and D.R. Guichard. The number of maximal indepen- dent sets in a connected graph. Discrete Mathematics., 68:211–220, 1988. [5] J. Hassan, AR. Bakkang, and ASS. Sappari. j2-hop domination in graphs: Properties and connections with other parameters. Eur. J. Pure Appl. Math., 16(4):2118–2131, 2023. [6] J. Hassan and S. Canoy Jr. Grundy dominating and grundy hop dominating sequences in graphs: Relationships and some structural properties. Eur. J. Pure Appl. Math., 16(2):1154–1166, 2023. [7] J. Hassan and S. Canoy Jr. Grundy total hop dominating sequences in graphs. Eur. J. Pure Appl. Math., 16(4):2597–2612, 2023. [8] J. Hassan, S. Canoy Jr., and A. Aradais. Hop independent sets in graphs. Eur. J. Pure Appl. Math., 15(2):467–477, 2022. [9] J. Hassan, A. Lintasan, and N.H. Mohammad. Some properties and realization prob- lems involving connected outer-hop independent hop domination in graphs. Eur. J. Pure Appl. Math., 16(3):1848–1861, 2023. [10] J. Hassan, J. Manditong, A. Bakkang, S. Kamdon, and J. Salim. Characterizations of j-total dominating sets of some graphs. Eur. J. Pure Appl. Math., 16(4):2106–2117, 2023. [11] J. Hassan, A. Tapeing, H. Copel, A.R Bakkang, and S.D. Aming. j2-independence parameters of some graphs. Eur. J. Pure Appl. Math., 17(1):124–134, 2024. [12] Liu Jiuqiang. Maximal and maximum independent sets in graphs. Dissertations., 1985. [13] S. Canoy Jr. and J. Hassan. Weakly convex hop dominating sets in graphs. Eur. J. Pure Appl. Math., 15(4):1783–1796, 2022. [14] S. Kaida, K.J. Maharajul, J. Hassan, L. S. Laja, A.B. Lintasan, and A.A. Pablo. Certified hop independence: Properties and connections with other variants of inde- pendence. Eur. J. Pure Appl. Math., 17(1):435–444, 2024. [15] J. Manditong, J. Hassan, LS Laja, AA. Laja, NHM. Mohammad, and SU. Kam- don. Connected outer-hop independent dominating sets in graphs under some binary operations. Eur. J. Pure Appl. Math., 16(3):1817–1829, 2023. [16] J. Manditong, A. Tapeing, J. Hassan, A.R. Bakkang, and N.H. Mohammadand S.U. Kamdon. Some properties of zero forcing hop dominating sets in a graph. Eur. J. Pure Appl. Math., 17(1):324–337, 2024. REFERENCES 930 [17] H.S. Wilf. The number of maximal independent sets in a tree. SIAM J. Alg. Disc. Meth., 7:125–130, 1986. [18] J. Zito. The structure and maximum number of maximum independent sets in trees. J. Graph Theory., 15(2):207–221, 1991.