EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
2025, Vol. 18, Issue 3, Article Number 6125
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Legal Closed Hop Neighborhood Independent
Sequences in Graphs

Javier A. Hassan1,2,∗, Farhadz A. Aripin1, Maria Andrea O. Bonsocan3,
Kimberly Jane Pon1, Vergel T. Bilar3

1Department of Mathematics, College of Arts and Sciences, MSU Tawi-Tawi College of
Technology and Oceanography, Bongao, Tawi-Tawi, Philippines
2Department of Mathematics, College of Science, Korea University, Seoul, South Korea
3Department of Mathematics, Ateneo de Davao University, Davao City, Philippines

Abstract. Let G be a graph. A sequence Q = (x1, x2, ..., xk) of distinct vertices of G is called a
legal closed hop neighborhood independent sequence (LCHNI sequence) if it satisfies the following

two conditions: [(i)] N2
G[xi] \

⋃i−1
j=1 N

2
G[xj ] ̸= for each i ∈ {2, 3, ..., k}, and [(ii)] dG(xs, xt) ̸= 1

for each s, t ∈ {1, 2, ..., k}, where s ̸= t. The legal closed hop neighborhood independence number
(LCHNI number) of G is the maximum length of an LCHNI sequence of G, and this is denoted by
θ(G). In this paper, the authors initiate the study of a legal closed hop neighborhood independent
sequence in some special graphs, shadow graphs, and the join of two graphs. In particular, the
authors determine the corresponding legal closed neighborhood independence numbers of these
graphs.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: Independent set, legal closed hop neighborhood independent sequence,
legal closed hop neighborhood independence number, co-legal closed neighborhood independent
sequence

1. Introduction

An independent set in a graph is a set of vertices such that no two vertices in the
set are adjacent to each other. This idea is crucial in various areas of graph theory and
its applications, including network design, scheduling problems, and resource allocation.
Independent sets in graphs have been studied on various types of graphs (see [1–9]).

In 2022, hop independent set in a graph and its corresponding parameter were intro-
duced and investigated by J. Hassan et al. [10]. This defined set stated that no two distinct

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v18i3.6125

Email addresses:
javierhassan@msutawi-tawi.edu.ph (J. A. Hassan),
farhadzaripin@msutawi-tawi.edu.ph (F. Aripin), maobonsocan@addu.edu.ph (M. A. Bonsocan),
kimberlyjanepon@msutawi-tawi.edu.ph (K. J. Pon), vtbilar@addu.edu.ph (V. Bilar)

https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0)



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 2 of 8

vertices in the set have a distance of two from each other. This was further investigated
on different types of graphs where they obtained some interesting results. Several variants
of this concept have been introduced and studied (see [11–14]).

More recently, inspired by numerous articles on independent sets of graphs, J. Hassan
et al. [11], introduced another variant of independent set called legal hop independent
sequence in a graph. This new variant added another property wherein the order of vertices
in the set of a graph matters, and is defined as follows: A sequence L = (w1, · · · , wk) of
distinct vertices of G is called a legal hop independent sequence if k = 1 or L is a hop
independent and NG[wi] \

⋃i−1
j=1NG[wj ] ̸= ∅ for every i ∈ {2, · · · , k}. The maximum

length of a legal hop independent sequence in G, denoted by αlh(G),is called the legal
hop independence number of G. The said authors have formulated characterizations and
formulas of this parameter on different types of graphs.

In this paper, a new variant of independence parameter is introduced and initially
investigated, and we call this legal closed hop neighborhood independent sequence (LCHNI
sequence) of a graph. In this parameter, the authors put some restrictions on the usual
independent set in a graph where the order of choosing vertices as well as the behavior of
its closed hop neighborhoods are important. The authors believe that this newly defined
parameter would open more interesting studies and applications in the future.

2. Terminologies and Notations

Let G be an undirected graph. A subset A of V (G) is an independent set if for
every pair of distinct vertices in A do not form an edge. The maximum cardinality of an
independent set in G, denoted by α(G), is called the independence number of G. Any
independent set with cardinality equal to α(G) is called an α-set in G.

Let G be an undirected graph. Let S = (v1, v2, · · · , vk) be a sequence of distinct
vertices of G and let Ŝ = {v1, v2, . . . , vk}. Then S is a legal closed hop neighborhood
sequence of G if N2

G[vi] \ ∪
i−1
j=1N

2
G[vj ] ̸= ∅ for each i ∈ {2, · · · , k}.

Let G be a graph. A sequence Q = (x1, x2, ..., xk) of distinct vertices of G is called
a legal closed hop neighborhood independent sequence (LCHNI sequence) if it is satisfies
the following two conditions:

(1.) N2
G[xi] \

⋃i−1
j=1N

2
G[xj ] ̸= for each i ∈ {2, 3, ..., k}.

(2.) dG(xs, xt) ̸= 1 for each s, t ∈ {1, 2, ..., k}, where s ̸= t.

The legal closed hop neighborhood independent number (LCHNI number) of G is the
maximum length of an LCHNI sequence in G. The said number is denoted by θ(G). We
call the corresponding set Q̂ an LCHNI set of G. We call the corresponding set Q̂ of Q an
LCHNI set of G.

Let Q1 = (v1, · · · , vn) and Q2 = (u1, · · · , um), n,m ≥ 1 be two sequences of distinct
vertices of G. The concatenation of Q1 and Q2, denoted by Q1⊕Q2, is the sequence given
by

Q1 ⊕Q2 = (v1, · · · , vn, u1, · · · , um).



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 3 of 8

Let G and H be any two graphs. The join 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 G ◦ H is the graph obtained by taking one copy of G and |V (G)|
copies of H, and then joining the ith vertex of G to every vertex of the ith copy of H. We
denote by Hv the copy of H in G ◦H corresponding to the vertex v ∈ G and write v+Hv

for ⟨{v}⟩+Hv.
The shadow graph S(G) of graph G is constructed by taking two copies of G, say G1

and G2, and then joining each vertex u ∈ V (G1) to the neighbors of its corresponding
vertex u′ ∈ V (G2).

3. Results

Remark 1. Let G be a graph. Then each of the following holds:

(i) A legal closed hop neighborhood sequence of G need not form an independent set of
G.

(ii) An independent set of G need not form a legal closed hop neighborhood sequence of
G.

(iii) A legal closed hop neighborhood independent sequence of G induces an independent
set of G.

(iv) 1 ≤ θ(G) ≤ α(G) ≤ |V (G)|.

Theorem 1. Let G be a graph of order n. Then θ(G) = |V (G)| if and only if G = Kn.

Proof. Suppose that G = Kn. Let V (Kn) = {c1, c2, ..., cn} = Q̂. Then, dKn
(ci, cj) =

∞ ≠ 1 for each i ̸= j where i, j ∈ {1, 2, ..., n}. This means that Q̂ is the maximum
independent set of Kn. Notice that

ci ∈ N2
Kn

[ci] \
i−1⋃
j=1

N2
K̄n

[cj ]

for each i ∈ {2, 3, ..., n}. It follows that Q = (c1, c2, ..., cn) is a legal closed hop neighbor-
hood sequence of Kn. Consequently, Q is the maximum legal closed hop neighborhood
independent sequence of Kn, and so θ(Kn) = |V (K̄n)|.

Conversely, assume that θ(G) = |V (G). Suppose further that G ̸= Kn. Then there
exist u, v ∈ V (G) such that dG(u, v) = 1. Hence, either u or v is not in any LCHNI set of
G, a contradiction to the assumption that α(G) = |V (G)|. Therefore, G must be equal to
Kn.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 4 of 8

Theorem 2. Let n be any positive integer. Then

θ(Pn) =


1, if n=1
n
2 , if n is even
n−1
2 , if n ≥ 3 and odd

Proof. By Theorem 1, θ(P1) = 1. Suppose that n is even. Clearly, θ(P2) = 1. Now,
for n ≥ 4, consider V (Pn) = {a1, a2, ..., an} and Q = {a1, a3, ..., an−3, an}. Then Q̂ is
a maximum independent set of Pn. Observe that ai+2 ∈ N2

G[ai] \
⋃

j<iN
2
G[aj ] for each

i ∈ {3, 5, ..., n − 3} and an ∈ N2
G[an] \

⋃
m<nN

2
G[am]. It follows that Q is an LCHNI

sequence of Pn. Therefore, Q is a maximum LCHNI sequence of Pn, and so θ(Pn) =
n
2 for

all even numbers n ≥ 2.
Next, suppose that n is an odd positive integer. For n = 3, let V (P3) = {b1, b2, b3}.

Since N2
P3
[b1] = N2

P3
[b3], it follows that θ(P3) = 1. Now, assume that n ≥ 5 and odd. Let

V (Pn) = {v1, v2, ..., vn}, and consider T = {v1, v3, ..., vn−2}. Then T̂ is an independent
set of Pn and vi+2 ∈ N2

G[vi] \
⋃

j<iN
2
G[vj ] for all i ∈ {3, 5, ..., n − 2}. Thus, T is an

LCHNI sequence of Pn. Since N
2
G[vn] ⊆ N2

G[vn−2], it follows that T is a maximum LCHNI
sequence of Pn. Consequently, θ(Pn) =

n−1
2 for all odd positive integers n ≥ 3.

Theorem 3. Let n ≥ 3 be any positive integer. Then

θ(Cn) =

{
α(Cn), if n is odd

α(Cn)− 1, if n is even

Proof. Suppose that n is odd. Clearly, for n = 3, θ(Cn) = 1. Now for n ≥ 5,
let V (Cn) = {c1, c2, ..., cn} and consider S = (c1, c3, ..., cn−2). Then Ŝ is a maximum
independent set of Cn. Notice that ci+2 ∈ N2

G[ci]\
⋃

j<iN
2
G[cj ] for each i ∈ {3, 5, ..., n−2}.

This means that S is a legal closed hop neighborhood sequence of Cn. Thus, S is a
maximum LCHNI sequence of Cn, and so θ(Cn) = α(Cn) for all odd numbers n ≥ 3.

Next, suppose that n is even. For n = 4, let V (C4) = {a1, a2, a3, a4}. Then N2
C4
[a1] =

N2
C4
[a3] and N2

C4
[a2] = N2

C4
[a4], where dc4(a1, a3) = 2 = dc4(a2, a4). It follows that

θ(C4) = 1.
For n = 6, let V (C6) = {b1, b2, ..., b6}.Notice that N2

c6 [b1] = N2
c6 [b3] = N2

c6 [b4] and
N2

c6 [b2] = N2
c6 [b4] = N2

c6 [b6], where dc6(b1, b3) = dc6(b3, b5) = dc6(b1, b5) = 2 and dc6(b2, b4) =
dc6(b4, b6) = dc6(b2, b6) = 2. This means that only one element in {b1, b3, b5} could be in
any legal closed hop neighborhood independent sequence of C6. Similarly, for the set
{b2, b4, b6}. Since dC6(b1, b1) = 1 = dC6(b1, b6), dC6(b1, b4) = 3, and N2

c6 [b4] \ N2
c6 [b1] =

{b2, b4, b6}, it follows that T = (b1, b4) is a maximum LCHNI sequence of C6, and so
θ(C6) = 2.

Now for n ≥ 8, let V (Cn) = {x1, x2, ..., xn} and consider W = {x1, x3, ..., xn−5, xn−2}.
Then Ŵ is an independent set of Cn with |Ŵ | = α(Cn) − 1. Notice that xi+2 ∈



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 5 of 8

N2
Cn

[xi] \
⋃

j<iN
2
Cn

[xj ] for all i ∈ {3, 5, ..., n − 5} and xn, xn−2, xn−4 ∈ N2
Cn

[xn−2] \⋃
j∈{1,3,...,n−5}N

2
Cn

[xj ]. Thus, W is a LCHNI sequence of Cn. Since

N2
Cn

[xn−3] ⊆ N2
Cn

[xn−5]
⋃

N2
Cn

[xi]

and
N2

Cn
[xn−1] ⊆ N2

Cn
[xn−5]

⋃
N2

Cn
[xi],

it follows that W is a maximum LCHNI sequence of Cn. Since M = {x1, x3, . . . , xn−1}
is a maximum independent set of Cn for all positive even integers n ≥ 4. It follows that
θ(Cn) = α(Cn)− 1 for all positive even numbers n ≥ 4.

The following concept will be used to study the behavior of LCHNI sequences in the
join of any two graphs.

Definition 1. Let G be a graph. Then a sequence P of distinct vertices of G is called a
co-legal closed neighborhood independent sequence (CLCNI sequence) of G if P is a legal
closed neighborhood sequence in Ḡ and P is an independent set of G.

The co-legal closed neighborhood independence number (CLCNI number) of G is the
maximum length of a CLCNI sequence of G, and is denoted by αcl(G).

The following theorem will be used to prove the characterization of an LCHNI sequence
on the join of two graphs.

Theorem 4. [15] Let G and H be any two graphs. A sequence S of distinct vertices of
G+H is a legal closed hop neighborhood sequence if and only if one of the following holds:

(i) S is a co-legal closed neighborhood sequence in G (legal closed neighborhood sequence
in G).

(ii) S is a co-legal closed neighborhood sequence in H (legal closed neighborhood sequence
in H).

(iii) S is a concatenation SG ⊕ SH , where SG and SH are co-legal closed neighborhood
sequences in G and H, respectively.

Theorem 5. Let G and H be any two graphs. Then a sequence F of distinct vertices
of G +H is an LCHNI sequence of G +H if and only if F satisfies any of the following
conditions:

(i) F is a CLCNI sequence of G.

(ii) F is a CLCNI sequence of H.

Proof. Suppose that F is an LCHNI sequence of G + H. Then F̂ is an independent
set of G + H. Thus, either F̂ is an independent set of G or F̂ is an independent set of
H. By Theorem 4, F is either a CLCNI sequence of G or H. Hence, F is either a CLCNI
sequence of G or H.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 6 of 8

Conversely, suppose that (i) holds. Then by Theorem 4, F is a legal closed hop
neighborhood sequence of G+H. Since F̂ is an independent set of G, it follows that F is
a LCHNI sequence of G+H. Similarly, the assertion holds when (ii) is true.

Theorem 6. Let G and H be any two graphs. Then θ(G+H) = max{αcl(G), αcl(H)}

Proof. We may assume that αcl(G) ≥ αcl(H). First, let P be a maximum LCHNI
sequence of G+H. Then by Theorem 3, P is a CLCNI sequence of G. Hence, θ(G+H) =
|P̂ | ≤ αcl(G).

Next, suppose that F is a maximum CLCNI sequence of G. Then F is an LCHNI
sequence of G + H by Theorem 3. It follows that θ(G + H) ≥ |F̂ | = αcl(G). This
establishes the desired equality.

Corollary 1. Let n and m be any two positive natural numbers. Then each of the following
holds:

(i) θ(Fn) = αcl(Pn)

(ii) θ(Wn) = αcl(Cn)

(iii) θ(Sn) = αcl(K̄n) = 1

(iv) θ(Pn + Pm) = max{αcl(Pn), αcl(Pm)}

(v) θ(Cn + Cm) = max{αcl(Cn), αcl(Cm)}

(vi) θ(Kn +Km) = max{αcl(Kn), αcl(Km)} = 1

Now, let’s study the behavior of an LCHNI sequence in the shadow graphs. We shall
note the following notations:

Let G1 and G2 be two copies of a graph G in the definition of the shadow graph S(G).
If QG1 ⊆ V (G1) and QG2 ⊆ V (G2), then the sets Q′

G1
and Q′

G2
are defined as follows:

Q′
G1

= {x′ ∈ V (G2) : x ∈ QG1} and Q′
G2

= {b ∈ V (G1) : b
′ ∈ QG2}.

Theorem 7. Let G be a non-trivial connected graph. Then Q is an LCHNI sequence in
S(G) if and only if one of the following conditions holds:

(i) Q is an LCHNI sequence in G1.

(ii) Q is an LCHNI sequence in G2.

(iii) Q = QG1 ⊕QG2 such that Q̂G1 ∪ Q̂′
G2

and Q̂′
G1

∪ Q̂G2 are LCHNI sets in G1 and G2,
respectively.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 7 of 8

Proof. Let Q be an LCHNI sequence in S(G). Let Q̂G1 = Q̂ ∩ V (G1) and Q̂G2 =
Q̂ ∩ V (G2). If Q̂G2 = ∅, then Q = QG1 is an LCHNI sequence in G1. Moreover, if
Q̂G1 = ∅, then Q = QG2 is an LCHNI sequence in G2. Therefore, either (i) or (ii) holds.

Now assume that Q̂G1 ̸= ∅ and Q̂G2 ̸= ∅. Let Q̂G1 ∪ Q̂′
G2

= {v1, v2, . . . , vk}, and
consider vi, vj ∈ Q̂G1 ∪ Q̂′

G2
and consider the following cases:

Case 1: If vi, vj ∈ Q̂G1 = Q̂∩V (G), then dG1(vi, vj) ̸= 1 since Q̂ is an independent set
in S(G) with Q̂G1 ⊆ Q̂.

Case 2: If vi, vj ∈ Q̂′
G2

, then v′i, v
′
j ∈ Q̂G2 . Since Q̂G2 ⊆ Q̂ and Q̂ is an independent,

it follows that dG2(vi, vj) ̸= 1, and we are done.

Case 3: Assume that vi ∈ Q̂G1 and vj ∈ Q̂′
G2

. Then v′j ∈ Q̂G2 ⊆ Q̂. Thus,
dS(G)(vi, vj) ̸= 1 implying that dG1(vi, vj) ̸= 1. Similarly, the same result follows when

vj ∈ Q̂G1 and vi ∈ Q̂′
G2

.

Now, let Q̂G1 = {vs : s ∈ S ⊆ {1, 2, . . . , k}} and Q̂′
G2

= {vt : t ∈ {1, 2, . . . , k} \ S}.
Then v′t ∈ Q̂G2 for all t ∈ {1, 2, . . . , vk} \ S. Since N2

S(G)[v
′
t] = N2

S(G)[vt] and Q is a legal

closed neighborhood sequence of S(G), it follows that N2
G[vi] \

⋃i−1
j=1N

2
G[vj ] ̸= ∅ for all

i ∈ {2, 3, . . . , k}. Thus, Q̂G1 ∪ Q̂′
G2

is an LCHNI set of G1. Similarly, Q̂′
G1

∪ Q̂G2 is an
LCHNI set of G2.

The converse is clear.

The following result follows from Theorem 7.

Corollary 2. Let G be a non-trivial connected graph. Then θ(S(G)) = θ(G).

4. Conclusion

The concept of legal closed hop neighborhood independent sequence has been intro-
duced and initially investigated in this study. Characterizations and formulas for the legal
closed hop neighborhood independence have been obtained on some special graphs, shadow
graphs, and on the join of any two graphs. Further exploration of this parameter on other
graphs under some operations, as well as its relationships with other parameters may
lead to deep insights and may show connections with other graph properties. Interested
researchers may provide a real-world application of the legal closed hop neighborhood
independent, and may investigate the complexity of this concept.

Acknowledgements

The authors would like to thank the referees for their respective invaluable comments
and suggestions. The authors are thankful to MSU Tawi-Tawi College of Technology and



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 18 (3) (2025), 6125 8 of 8

Oceanography, Korea University, and Ateneo de Davao University for the financial support
they have extended.

References

[1] E. Davies, M. Jenssen, W. Perkins, and B. Roberts. Independent sets, matchings,
and occupancy fractions. Journal of the London Mathematical Society, 96:211–220,
2017.

[2] E. Davies, M. Jenssen, W. Perkins, and B. Roberts. On the average size of indepen-
dent sets in triangle-free graphs. Proceedings of the American Mathematical Society,
146(1):111–124, 2018.

[3] Z. Füredi. The number of maximal independent sets in connected graphs. Journal of
Graph Theory, 11(4):463–470, 1987.

[4] J. R. Griggs, C. M. Grinstead, and D. R. Guichard. The number of maximal inde-
pendent sets in a connected graph. Discrete Mathematics, 68:211–220, 1988.

[5] G. Hopkins and W. Staton. Graphs with unique maximum independent sets. Discrete
Mathematics, 57:245–251, 1985.

[6] D. G. C. Horrocks. Doubly independent sets in graphs. Australasian Journal of
Combinatorics, 22:105–116, 2000.

[7] D. S. Johnson, M. Yannakakis, and C. J. Papadimitriou. On generating all maximal
independent sets. Information Processing Letters, 27:119–123, 1988.

[8] H. S. Wilf. The number of maximal independent sets in a tree. SIAM Journal on
Algebraic and Discrete Methods, 7:125–130, 1986.

[9] J. Zito. The structure and maximum number of maximum independent sets in trees.
Journal of Graph Theory, 15(2):207–221, 1991.

[10] J. Hassan, S. Canoy Jr., and A. Aradais. Hop independent sets in graphs. European
Journal of Pure and Applied Mathematics, 15(2):467–477, 2022.

[11] J. Hassan, M. Langamin, A. Laja, B. Amiruddin-Rajik, E. Ahmad, and J. Manditong.
Legal hop independent sequences in graphs. European Journal of Pure and Applied
Mathematics, 17(2):725–735, 2024.

[12] J. Hassan, A. Tapeing, H. Copel, A. Bakkang, and S. D. Aming. j2-independence
parameters of some graphs. European Journal of Pure and Applied Mathematics,
17(1):124–134, 2024.

[13] J. Hassan, N. Bakar, N. Dagsaan, M. Langamin, and N. H. Mohammad. j-open
independent sets in graphs. European Journal of Pure and Applied Mathematics,
17(2):922–930, 2024.

[14] S. Kaida, K. J. Maharajul, J. Hassan, L. Laja, A. Lintasan, and A. Pablo. Certified
hop independence: Properties and connections with other variants of independence.
European Journal of Pure and Applied Mathematics, 17(1):435–444, 2024.

[15] J. Hassan and S. Canoy Jr. Grundy hop domination in graphs. European Journal of
Pure and Applied Mathematics, 15(4):1623–1636, 2022.