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

L-Hop Independent Sequences in Graphs

Kaimar Jay S. Maharajul1, Javier A. Hassan1,2,∗, Ladznar S. Laja1

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

Abstract. Let G be a graph. A sequence of distinct vertices Q = (a1, a2, . . . , an) of G is called an
L-hop independent sequence if n = 1 or if dG(ai, aj) ̸= 2 for each i ̸= j, where i, j ∈ {1, 2, . . . , n}

and NG[as]\
s−1⋃
t=1

NG(at) ̸= ∅ for each s ∈ {2, . . . , n}. The L-hop independence number of G,

denoted by αLh(G), is the maximum length among all L-hop independent sequences in G. This
study explores and characterizes the L-hop independent sequences in some graphs, and in the join
of two graphs. Some formulas and bounds of L-hop independence number with respect to the
order of a graph and other parameters in graph theory are derived. Moreover, some relationships
of L-hop independence with hop independence and legal hop independence are established.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: L-sequence, clique L-sequence, clique L-Grundy dominating sequence,
L-hop independent sequence, L-independence number

1. Introduction

Graph Theory is relatively new area of mathematics, first studied by the super famous
mathematician Leonhard Euler in 1735. Since then it has blossomed into a powerful tool
used in nearly every branch of science and is currently an active area of mathematics
research.

One of the hottest topics in Graph Theory is the concept of independent sets in graphs.
A set S ⊆ V (G) is called an independent set of G if no two pair of distinct vertices of
S are adjacent. The maximum cardinality of an independent set of G, denoted by α(G),
is called the independence number of G [1]. The concept of an independent set is often
studied in the context of maximum independent sets, which refers to the largest possible

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

Email addresses:
kaimarjaymaharajul@msutawi-tawi.edu.ph (K. J. Maharajul)
javierhassan@msutawi-tawi.edu.ph (J. A. Hassan).
ladznarlaja@msutawi-tawi.edu.ph (L. S. Laja)

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



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 2 of 10

independent set within a graph. This set has applications in areas like scheduling, resource
allocation, and even social network analysis, where finding independent sets can represent
groups of individuals or resources that do not interfere with one another.

In 2022, hop independent set in a graph and its parameter was introduced by J.
Hassan et al. [2]. A set S ⊆ V (G) is called a hop independent set of G if dG(u,w) ̸= 2
for any distinct vertices u,w ∈ S. The maximum cardinality of a hop independent set
of G, is called the hop independence number of G, and is denoted by αh(G). They have
shown that the hop independence number of a graph is always greater than or equal to
the hop domination number. Moreover, they derived some bounds and formulas of hop
independence numbers of some special graphs and graphs under some binary operations.
Some studies related to independent sets, its variations, and other hop-related concepts
can be found in [3–11].

In this paper, new variant of hop independence called L-hop independence sequence
in a graph is introduced. The authors add some properties to hop independence wherein
the order of choosing vertices and its neighborhoods are important. This parameter is
investigated on some special graphs, and on the join of any two graphs. Some bounds
and exact values are determined. Moreover, some characterizations of this newly defined
sequence are presented, and used to solve the said bounds and exact values. The authors
are confident that this study would lead to another interesting studies and application 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.

A subset I of V (G) is called an independent if for every pair of distinct vertices x, y ∈ I,
dG(x, y) ̸= 1. The maximum cardinality of an independent set in G, denoted by α(G), is
called the independence number of G. Any independent set I 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 dG(u, v) ̸= 2 for any two
distinct vertices u, v ∈ S. The hop independence number of G, denoted by αh(G), is the
maximum cardinality of a hop independent set of G.

Given a graph G and a sequence S = (v1, . . . , vk) of distinct vertices of G, for every

i ∈ {2, 3, · · · , k} we define the set ϕs by ϕs(V i) = N [Vi]\
i−1⋃
j=1

N(Vj). The sequence is called

L-sequence if ϕs(Vi) ̸= ∅ for every i ∈ {2, 3, · · · , k}.
Let S1 = (v1, . . . , vn) and S2 = (u1, . . . , um) be two sequences of distinct vertices

of G. The concatenation of S1 and S2, denoted by S1 ⊕ S2, is the sequence given by
S1 ⊕ S2 = (v1, . . . , vn, u1, . . . , um).

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



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 3 of 10

by αℓh(G), is called the legal hop independence number of G.
A graph is complete if every pair of distinct vertices are adjacent. A complete graph

of order n is denoted by Kn. A set S ⊆ V (G) is called a clique in G if the subgraph
⟨S⟩ induced by S is a complete graph. The maximum size or cardinality of a clique of G,
denoted by ω(G), is called the clique number of G.

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)}.

3. Results

We shall now define the L-hop independent sequence and L-hop independence number
of a graph as follows:

Definition 1. Let G be a graph. A sequence of distinct vertices Q = (a1, a2, . . . , an) of
G is called an L-hop independent sequence if n = 1 or if dG(ai, aj) ̸= 2 for each i ̸= j,

where i, j ∈ {1, 2, . . . , n} and NG[as]\
s−1⋃
t=1

NG(at) ̸= ∅ for each s ∈ {2, . . . , n}. The L-

hop independence number of G, denoted by αLh(G), is the maximum length among all
L-hop independent sequences in G. Moreover, we call Q̂ = {a1, a2, · · · , ak} an L−hop
independent set of G.

Example 1. Consider the graph in Figure 1. Let L = (a1, a2). Then dP4(a1, a2) = 1.
Observe that NP4(a1) = {a2} and NP4 [a2] = {a1, a2, a3}. Thus,

NP4 [a2]\NP4(a1) = {a1, a2, a3}\{a2} = {a1, a3} ≠ ∅.

Therefore, L = (a1, a2) is an L-hop independent sequence of P4, and so
αLh(P4) ≥ 2. Now, since dP4(a1, a3) = 2, it follows that αLh(P4) ̸= 4. Since

dP4(a1, a3) = 2 = dP4(a2, a4),

it follows that L is a maximum L-hop independent sequence of P4. Therefore, αLh(P4) = 2.

a1 a2 a3 a4P4 :

Figure 1: A path graph of order 4.



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 4 of 10

Theorem 1. Let G be a graph. Then

i. αLh(G) ≤ αh(G);

ii. 1 ≤ αLh(G) ≤ |V (G)|; and

iii. αLh(G) ≥ αℓh(G).

Proof. [i.] Let G be a graph and let D be a maximum L-hop independent sequence of
G. Then αLh(G) = |D̂| and D̂ is a hop independent set of G, where D̂ is a corresponding
set of D. Since, αh(G) is the maximum cardinality among all hop independent sets in G,
it follows that αh(G) ≥ |D̂ = αLh(G).

[ii.] Since any sequence (v), where v ∈ V (G), is an L-hop independent sequence of
G, we have αLh(G) ≥ 1. Since αh(G) ≤ |V (G)|, it follows that αLh(G) ≤ |V (G)| by (i).
Consequently, 1 ≤ αLh(G) ≤ |V (G)|.

[iii.] Let S = (v1, v2, . . . , vn) be a maximum legal hop independent sequence in G. Then

NG[vi]\
i−1⋃
j=1

NG[vj ] ̸= ∅ for each i ∈ {2, 3, . . . , n}. Since NG(a) ⊆ NG[a] for all a ∈ V (G), it

follows that ∅ ̸= NG[vi]\
i−1⋃
j=1

NG[vj ] ⊆ NG[vi]\
i−1⋃
j=1

NG(vj). Hence, NG[vi]\
i−1⋃
j=1

NG(vj) ̸= ∅

for each i ∈ {2, 3, . . . , n}. Therefore, S is an L-sequence in G. Since Ŝ is a hop independent
set of G, it follows that S is an L-hop independent sequence in G. Since αLh(G) refers
to the maximum length of an L-hop independent sequence in G, it follows that αLh(G) ≥
|Ŝ| = αℓh(G).

Remark 1. The strict inequality of Theorem 1(i) is attainable. Moreover, the inequality
is also attainable.

Consider the following two examples below:

Example 2. Consider the graph G below.

G :

x1 x2

x3 x4

Let S = {x1, x2, x3, x4}. Then S is a maximum hop independent set of G. Thus,
αh(G) = 4. Next, let B = (x1, x2). Then NG[x2] = V (G) and NG(x1) = {x2, x3, x4}.
Hence, NG[x2] \ NG(x1) = {x1} ̸= ∅, showing that B is an L-hop independent sequence
of G. Since NG(xi) ∪NG(xj) = V (G) for all i, j ∈ {1, 2, 3, 4}, where i ̸= j, it follows that
B is a maximum L-hop independent sequence of G . That is, αLh(G) = 2.



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 5 of 10

Example 3. Consider the graph G′ below.

G′ :

x1 x2

x3

x4

x5

x8 x9

x7

x10

x11x6 x12

Let P = (x1, x2, x5, x6, x8, x9, x11, x12) and let P̂ = {x1, x2, x5, x6, x8, x9, x11, x12}.
Then P̂ is a maximum hop independent set of G′ and P is a maximum L-hop independent
sequence of G′. Therefore, αh(G

′) = 8 = αLh(G
′).

We shall now state the following remark:

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

(i) Every legal hop independent sequence of G is an L-hop independent sequence.

(ii) Every L-hop independent set is a hop independent set, however, the converse need
not be true.

Proposition 1. Let n be a positive integer. Then

αLh(Kn) =

{
1 if n = 1

2 if n ≥ 2.

Proof. Clearly, αLh(K1) = 1. For n = 2, let V (K2) = {v1, v2}. Then
NK2 [v2] = {v1, v2} and NK2(v1) = v2. Thus, NK2 [v2]\NK2(v1) = v1 ̸= ∅, showing that
C = (v1, v2) is an L-sequence of K2. Since dK2(v2, v1) = 1, it follows that C is an L-hop
independent sequence of K2. Therefore, αLh(K2) = 2. Next, suppose that n ≥ 3. Let
V (Kn) = {v1, v2, . . . , vn}. Then C ′ = (v1, v2) is an L-hop independent sequence of Kn.
Hence, αLh(Kn) ≥ 2. Suppose that αLh(Kn) ≥ 3, say L = (v1, v2, . . . , vm) is a maximum
L-hop independent sequence of Kn, where m ≥ 3. Note that NKn(v1)∪NKn(v2) = V (Kn).

It follows that NKn [vs]\
s−1⋃
i=1

NKn(vi) = ∅ for all 3 ≤ s ≤ m, a contradiction. Therefore,

αLh(Kn) = 2 for all n ≥ 2.

Proposition 2. Let G be a graph. If αLh(G) = |V (G)|, then αh(G) = |V (G)|. However,
the converse is not necessarily true.



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 6 of 10

Proof. Suppose that αLh(G) = |V (G)|. Then αh(G) ≥ |V (G)| by Theorem 1. Since
αh(G) ≤ |V (G)|, it follows that αh(G) = |V (G)|.

Now, consider K5 and let V (K5) = {x1, x2, x3, x4, x5}. Observe that
dK5(xi, xj) = 1 for all i, j ∈ {1, 2, 3, 4, 5}, where i ̸= j. It follows that V (K5) is a maximum
hop independent set of K5. Thus, αh(K5) = 5. Now, by Proposition 1, αLh(K5) = 2.
Hence, the assertion follows.

Theorem 2. [2] Let G be any graph on n vertices. Then

i. αh(G) = n if and only if every component of G is complete; and

ii. for n ≥ 3, αh(G) = n − 1 if and only if all but a single component C of G are
complete and C\v is a complete graph for some vertex v ∈ V (C).

Theorem 3. Let G be a graph. Then αLh(G) = |V (G)| if and only if every component
of G is either K1 or K2.

Proof. Suppose that αLh(G) = |V (G)|. Then by Proposition 2, αh(G) = |V (G)|. By
Theorem 2(i) , every component of G is complete. If it is either K1 or K2, then we are
done. Now, suppose that every component of G is Kn, where n ≥ 3. Then by Proposition
1, αLh(Kn) = 2 for all n ≥ 3. It follows that αLh(G) ≤ |V (G)| − 1, a contradiction.
Therefore, the assertion is true.

Conversely, suppose that every component of G is either K1 or K2. If every component
of G is K1. Then by Theorem 1, αLh(K1) = 1. Let m be the number of components K1

of G. Then αLh(G) =

m∑
i=1

αLh(K1) = m = |V (G)|. Next, assume that every component

of G is K2. Then by Proposition 1, αLh(K2) = 2. Let s be the number of components

K2 of G. Then αLh(G) =
s∑

j=1

αLh(K2) = 2s = |V (G)|. Now, let r and q be the number

of K1 and K2 components of G, respectively. Then by Proposition 1, αLh(G) = r + q =
|V (G)|.

Corollary 1. (i) Let n be a positive integer. Then αLh(Kn) = n for all n ≥ 1.

(ii) αLh(G) = αh(G) = |V (G)| if and only if every component of G is either K1 or K2.

To characterize the L-hop independent sequences and the join of two graphs, we first
define the following concepts:

Definition 2. Let G be a graph. A sequence L = (a1, . . . , an) of distinct vertices of
G is called a clique L-sequence if n = 1 or if L is an L-sequence and its corresponding
set L̂ = {a1, a2, · · · , an} induces a complete graph. The maximum length of a clique L-
sequence in G, denoted by αL

ch(G), is called the L-clique number of G. Moreover, we call

L̂ a clique L-set of G.



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 7 of 10

Definition 3. Let G be any graph. A clique L-sequence L is called a clique
L-dominating sequence or a clique L-Grundy dominating sequence if its corresponding
set L̂ is a dominating set of G. The maximum length of a clique L-Grundy domi-
nating sequence in G, denoted by γLcgr(G), is called the clique L-Grundy domination
number of G. Moreover, a clique L-sequence L of G is called a clique non-dominating
L-sequence if L̂ is not a dominating set of G.

Theorem 4. [2]Let G and H be graphs. Then S is a non-empty hop independent set of
G+H if and only if one of the following statement holds:

(i) S ∩ V (H) = ∅ and S ∩ V (G) is a clique of G.

(ii) S ∩ V (G) = ∅ and S ∩ V (H) is a clique of H.

(iii) S ∩ V (G) and S ∩ V (H) are cliques in G and H, respectively.

Theorem 5. [12] Let G and H be two non-complete graphs. A sequence D of distinct
verices of G + H is a Grundy dominating sequence in G + H if and only if one of the
following conditions holds:

(i) D is a Grundy dominating sequence of G.

(ii) D is a Grundy dominating sequence of H.

(iii) D = DG ⊕ (w) for some non-dominating legal closed neighborhood sequence DG of
G and w ∈ V (H).

(iv) D = DH ⊕ (v) for some non-dominating legal closed neighborhood sequence DH of
H and v ∈ V (G).

Theorem 6. Let H and K be two non-complete graphs. A sequence A of distinct vertices
of H +K is an L-hop independent sequence in H +K if and only if one of the following
conditions holds:

(i) A is a clique L-sequence in H

(ii) A is a clique L-sequence in K

(iii) A = AH⊕(a), where AH is a clique non-dominating L-sequence in H and a ∈ V (K).

(iv) A = AK ⊕ (b), where AK is a clique non-dominating L-sequence in K and b ∈ V (H).

(v) A = (x, y) for some x ∈ V (H) and y ∈ V (K).

Proof. Suppose that A is a L-hop independent sequence of H + K. Assume that
 ⊆ V (H). Then  is a clique in H by Theorem 4. By Theorem 5, A is a legal sequence
in H. Thus, A is an L-sequence in H, showing that A is a clique L-sequence in H, that



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 8 of 10

is, (i) holds. Similarly, if  ⊆ V (K), then A is a clique L-sequence inK. That is, (ii) holds.

Now, let AH and AK be subsequences of A such that ÂH = Â ∩ V (H) and ÂK =
 ∩ V (K), where ÂH ̸= ∅ and ÂK ̸= ∅. Then A = AH ⊕ (a) for some non-dominating
legal sequence AH in H and a ∈ V (K) by Theorem 5. Since every legal sequence is an
L-sequence, AH is a non-dominating L-sequence in H. By Theorem 4, AH is clique in H.
Thus, AH is a clique non-dominating L-sequence in H, and so (iii) holds. Similarly, by
Theorem 4 and Theorem 5, (iv) holds. Now, it is also easy to see that (v) follows whenever
AH or AK is a clique L-Grundy dominating sequence of H or K.

Conversely, assume that (i) holds. Then by Theorem 4, Â is a hop independent set
of H +K. Since A is an L-sequence, it follows that A is an L-hop independent sequence
of H + K. Similarly, the assertion follows whenever (ii) holds. Suppose that (iii) holds.
Then the corresponding set of AH ⊕ (a) is a hop independent set of H +K. Since AH is
a non-dominating, there exists x ∈ V (H) \ ÂH such that x /∈ NH+K(ÂH). It follows that
x ∈ NH+K [a] \ NH+K(ÂH). Thus, A = AH ⊕ (a) is an L-hop independent sequence of
H+K. Similarly, the result follows when (iv) is true. Moreover, it is clear that A = (x, y)
for some x ∈ V (H) and y ∈ V (K) is an L-hop independent sequence of H +K.

Theorem 7. [12]Let G be a complete graph and let H be a non-complete graph. A
sequence D of distinct vertices of G + H is a Grundy dominating sequence in G + H if
and only if one of the following condition holds:

(i) D = (v) for some v ∈ V (G).

(ii) D is a Grundy dominating sequence of H.

(iii) D = DH ⊕ (v) for some non-dominating legal closed neighborhood sequence DH of
H and v ∈ V (G).

Theorem 8. Let Q and R be complete and non-complete graph, respectively. A sequence
B of distinct vertices of Q+R is an L-hop independent sequence if and only if one of the
following conditions holds:

(i) B is a clique L-sequence of Q.

(ii) B is a clique L-sequence of R.

(iii) B = BR ⊕ (w), where BR is a clique non-dominating L-sequence in R and
w ∈ V (Q).

(iv) A = (x, y) for some x ∈ V (H) and y ∈ V (K).

Proof. Let B be an L-hop independent sequence of Q + R. Assume that B̂ ⊆ V (Q).
Since B̂ is hop independent in Q+ R, B̂ is clique in R by Theorem 4. Hence, (i) follows
since B is an L-sequence in Q+R. Similarly, (ii) follows whenever B̂ ⊆ V (R) .



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 9 of 10

Now, assume that B̂ = B̂Q∪ B̂R, where B̂q = B̂∩V (Q) ̸= ∅ and B̂R = B̂∩V (R) ̸= ∅.
By Theorem 7, B = BR ⊕ (w) for some non-dominating legal closed neighborhhood se-
quence BR of R and w ∈ V (Q). Since every legal closed neighborhood sequence is an
L-sequence and B̂ is a hop independent set in Q+R, BR must be a clique non-dominating
L-sequence in R. Hence, (iii) holds.

The converse can be proved easily.

The following Theorem can be proved easily.

Theorem 9. Let Q and R be complete graphs. A sequence B of distinct vertices of Q+R
is an L-hop independent sequence if and only if one of the following conditions holds:

(i) B is a clique L-sequence of Q.

(ii) B is a clique L-sequence of R.

(iii) A = (x, y) for some x ∈ V (H) and y ∈ V (K).

The following result follows from Proposition 1, Theorem 6, Theorem 8, and Theorem
9.

Corollary 2. Let H and K be two graphs. Then

(i) 2 ≤ αLh(H +K) ≤ 3; and

(ii) αLh(H +K) = 2 if both H and K are complete graphs.

4. Conclusion

The concept of L-hop independent sequence has been introduced and initially inves-
tigated in this study. Some characterizations and formulas have been obtained on some
special graphs, complementary prism, and on the join of any two graphs. Interested re-
searchers may consider studying the complexity of this newly defined concept, and they
may also consider providing real-world applications.

Acknowledgements

The authors would like to thank Mindanao State University-Tawi-Tawi College of
Technology and Oceanography and Korea University for funding this research.

References

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



K. Maharajul, J. A. Hassan, L. Laja / Eur. J. Pure Appl. Math, 18 (3) (2025), 6383 10 of 10

[2] 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.

[3] Z. Furedi. 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] 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.

[6] 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.

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

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

[9] M. Jou and G. Chang. The number of maximum independent sets of graphs. Tai-
wanese Journal of Mathematics, 4(4):685–695, 2000.

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

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

[12] J. Hassan and S. Canoy Jr. Grundy dominating and grundy hop dominating sequences
in graphs: Relationships and some structural properties. European Journal of Pure
and Applied Mathematics, 16(2):1154–1166, 2023.