EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 17, No. 1, 2024, 435-444
ISSN 1307-5543 – ejpam.com
Published by New York Business Global

Certified Hop Independence: Properties and
Connections with Other Variants of Independence

Sharmia H. Kaida1, Kaimar Jay S. Maharajul1, Javier A. Hassan1,∗,
Ladznar S. Laja1, Abdurajan B. Lintasan1, Aljon A. Pablo2

1Mathematics and Sciences Department, College of Arts and Sciences, MSU-Tawi-Tawi
College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines
2 Banaran Main Junior High School, Secondary Education Department, MSU-Tawi-Tawi
College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines

Abstract. Let G be a graph. Then B ⊆ V (G) is called a certified hop independent set of G if
for every a, b ∈ B, dG(a, b) ̸= 2 and for every x ∈ B has either zero or at least two neighbors
in V (G) \ B. The maximum cardinality among all certified hop independent sets in G, denoted
by αch(G), is called the certified hop independence number of G. In this paper, we initiate the
study of certified hop independence in graphs and we establish some of its properties. We give
realization results involving hop independence and certified hop independence parameters, and
we show that the difference between these two parameters can be made arbitrarily large. We
characterize certified hop independent sets in some graphs and we use these results to obtain the
exact values or bounds of the parameter. Moreover, we show that the certified hop independence
and independence parameters are incomparable.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: Hop independence, certified independent set, certified hop indepen-
dence number

1. Introduction

In this paper, we introduce a new variant of hop independence called certified hop
independence. Indeed, while a hop independent set of a graph requires that no two distinct
vertices in the set are at distance two from each other, the concept that we will be dealing
with here imposes additional condition that each vertex in the set must have either zero

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i1.5044

Email addresses: sharmiakaida@msutawi-tawi.edu.ph (S. Kaida)
kaimarjaymaharajul@msutawi-tawi.edu.ph (K. Maharajul)
javierhassan@msutawi-tawi.edu.ph (J. Hassan)
ladznarlaja@msutawi-tawi.edu.ph (L. Laja)
abdurajanlintasan@msutawi-tawi.edu.ph (A. Lintasan)
aljonpablo@msutawi-tawi.edu.ph (A. Pablo)

https://www.ejpam.com 435 © 2024 EJPAM All rights reserved.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 436

or at least two neighbors outside the set. Some related studies on hop independence can
be found in [1–4].

The motivation of introducing the concept is the ever increasing number of studies on
independence and some of its variations. We show that the certified hop independence and
the standard independence parameters of a graph are incomparable. Moreover, we give
realization results involving certified hop independence and hop independence parameters,
and we show that the latter is always at most equal to the hop independence parameter.

2. Terminology and Notation

Let G = (V (G), E(G)) be a simple and undirected graph. 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 in G is the
set NG[x] = NG(x) ∪ {x}. If X ⊆ 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 path graph is 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 called 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}.

A graph is complete if every pair of distinct vertices are adjacent. A complete graph
of order n is denoted by Kn. A subset C of a vertex-set V (G) of G is a clique if the graph
⟨C⟩ induced by C is complete. The maximum cardinality of a clique of G, denoted by
ω(G), is called the clique number of G.

A graph G is connected if every pair of its vertices can be joined by a path. Otherwise,
G is disconnected. A maximal connected subgraph (not a subgraph of any connected
subgraph) of G is called a component of G.

Let G and H be two graphs. The join G+H of G and H is the graph with vertex set
V (G+H) = V (G) ∪ V (H) and edge set

E(G+H) = E(G) ∪ E(H) ∪ {ab : a ∈ V (G), b ∈ V (H)}.

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.

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 any two distinct vertices
in S are not at distance two from each other, that is, dG(v, w) ̸= 2 for any two distinct
vertices v, w ∈ S. The hop independence number of G, denoted by αh(G), is the maximum



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 437

cardinality of a hop independent set of G.

3. Results

We begin this section by introducing the concept of certified hop independence in a
graph.

Definition 1. Let G be a graph. Then B ⊆ V (G) is called a certified hop independent set
of G if for every a, b ∈ B, dG(a, b) ̸= 2 and for every x ∈ B has either zero or at least two
neighbors in V (G) \ B. The maximum cardinality among all certified hop independent
sets in G, denoted by αch(G), is called the certified hop independence number of G. Any
certified hop independent set B with |B| = αch(G) is called the maximum certified hop
independent set of G or an αch-set of G.

Example 1. Consider the graph G in Figure 1.

G :

a

f b

e c

d

Figure 1: Graph G with αch(G) = 2

Let B = {a, d}. Then dG(a, d) = 3. Thus, B is a hop independent set of B. Now, observe
that b, f ∈ NG(a) and c, e ∈ NG(d), where b, c, f, e ∈ V (G) \ B. It follows that B is a
certified hop independent set of G. Moreover, it can be verified that αch(G) = 2.

Theorem 1. Let G be a graph. Then

(i) αch(G) ≤ αh(G); and

(ii) 1 ≤ αch(G) ≤ |V (G)|.

Proof. (i) Let B ⊆ V (G) be a maximum certified hop independent set of G. Then
αch(G) = |B| and B is a hop independent set of G. Since αh(G) is the maximum cardi-
nality among all hop independent sets in G, it follows that αh(G) ≥ |B| = αch(G).

(ii) Since an empty set cannot be a certified hop independent, we have αch(G) ≥ 1.
Since αh(G) ≤ |V (G)|, we have αch(G) ≤ |V (G)| by (i). Consequently,

1 ≤ αch(G) ≤ |V (G)|.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 438

Theorem 2. Let G be a graph. Then αch(G) = |V (G)| if and only if diam(H) ≤ 1 for
each component H of G.

Proof. Suppose that αch(G) = |V (G)|. Then V (G) is the maximum certified hop
independent set of G. Assume that G is connected. Suppose further that diam(G) ≥ 2.
There exist a, b ∈ V (G) such that dG(a, b) = 2. This means that a and b cannot be
both elements of any certified hop independent set of G. Thus, αch(G) ≤ |V (G)| − 1, a
contradiction. Next, suppose that G is disconnected. Suppose further that diam(H) ≥ 2
for some component H of G. Then there exist x, y,∈ V (H) such that

dH(x, y) = 2 = dG(x, y).

Then either x or y cannot be an element of a certified hop independent set of G. Thus
αch(G) ≤ |V (G)| − 1, a contradiction. Therefore, diam(H) ≤ 1 for each component H of
G.

Conversely, suppose that diam(H) ≤ 1 for each component H of G. Let u, v ∈ V (G).
If u, v are vertices of one component K of G, then dK(u, v) = 1 = dG(u, v), and we are
done. Suppose that u ∈ V (Q) and v ∈ V (T ), where Q and T are components of G. Then
dG(u, v) ̸= 2. Since u and v are arbitrary, it follows that V (G) is a hop independent set
of G. Since each vertex in G has zero neighbor outside V (G), V (G) is a certified hop
independent set of G. Consequently, αch(G) = |V (G)|.

Corollary 1. Let m be a positive integer. Then αch(Km) = m = αch(Km) for all m ≥ 1.

Theorem 3. If S is a certified hop independent set of a path graph Pn, then dPn(x, y) ≥ 3
for all x, y ∈ S, where x ̸= y.

Proof. let S ⊆ V (Pn) be a certified hop independent set of Pn, where
V (Pn) = {v1, v2, . . . , vn}. Let x, y ∈ S. Suppose that dpn(x, y) = 1. If x = v1, then
y = v2 and y have only one neighbor v3 outside S, a contradiction. Similarly, when y = v1,
x = vn or y = vn. Suppose that x = vi and y = vj , where i, j = {2, . . . , n − 1}. Since
|NPn(vk)| = 2 for all k ∈ {2, . . . , n− 1}, x and y have only one neighbor outside S, which
is a contradiction. Now, since any certified hop independent set is a hop independent, it
follows that dPn(x, y) ̸= 2. Therefore, dPn(x, y) ≥ 3 for all x, y ∈ S, where x ̸= y.

The following result follows from Theorem 3.

Corollary 2. Let n be a positive integer. Then

αch(Pn) =

{
n if n = 1, 2

⌊n3 ⌋ if n ≥ 3.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 439

Theorem 4. If S′ is a certified hop independent set of a cycle graph Cn, then dCn(u, v) ≥ 3
for all u, v ∈ S′, where u ̸= v.

Proof. Let S′ ⊆ V (Cn) be a certified hop independent set of Cn. Let u, v ∈ S′. If
dCn(u, v) = 1, then both u and v have only one neighbor in V (Cn) \ S′, a contradiction.
Now, since S′ is a hop independent set of Cn, dCn(u, v) ̸= 2 for all u, v ∈ S′. Therefore,
dCn(u, v) ≥ 3 for all u, v ∈ S′, where u ̸= v.

The following result follows from Theorem 4.

Corollary 3. Let n be a positive integer. Then

αch(Cn) =

{
n if n = 3

⌊n3 ⌋ if n ≥ 4.

The following is a realization results involving certified hop independence and hop
independence parameters.

Theorem 5. Let a and b be positive integers such that 2 ≤ a ≤ b. Then there exists a
connected graph G such that αch(G) = a and αh(G) = b.

Proof. Consider the following two cases:

Case 1 : a = b

Subcase 1 : a ≥ 5 is odd
Consider the graph G in Figure 2.

G :
. . .

x1

x2

x3

x4

xa−3
xa−1

xa−4 xaxa−2

Figure 2: Graph G with αch(G) = a = αh(G).

Let B1 = {x1, x2, ..., xa−1, xa}. Then B1 is both a maximum certified hop independent
and a maximum hop independent set of G. Thus,

αch(G) = a = αh(G).

Next, for a = 3 = b, consider K3. Then αch(K3) = a = αh(K3).



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 440

Subcase 2 : a is even
Consider the graph G′ below.

G′ :
. . .

y1

y2

y3

y4

ya−3
ya−1

ya−2 ya

Figure 3: Graph G′ with αh(G
′) = a = αch(G

′)

Let B2 = {y1, y2, . . . , ya}. Then B2 is both a maximum hop independent and a maxi-
mum certified hop independent set of G. Therefore, αh(G

′) = a = αch(G
′).

Case 2 : a < b
Let m = b− a and consider the following cases.

Subcase 1 : a is odd.
Consider the graph H below.

x1

x2

xa−2

xa−1

u

xa

ym

y2

y1

H :
. . .

...

Figure 4: Graph H with αch(H) < αh(H)

Let B′ = {x1, x2, ..., xa} and B′′ = {x1, x2, ..., xa−1, u, y1, y2, ..., ym}. Then B′ and
B′′ are maximum certified hop independent and maximum hop independent set of H,
respectively. Hence, αch(H) = a and αh(H) = a+m = b.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 441

Case 2 : a is even
Consider the graph H ′ below.

x1

x2

xa−3

xa−2

v

xa−1

ym+1

y2

xa

H ′ :
. . .

.

.

.

y1

Figure 5: Graph H′ with αch(H
′) < αh(H

′)

Let C1 = {x1, x2, ..., xa} and C2 = {x1, x2, ..., xa−2, v, y1, y2, ..., ym+1}. Then C1 and
C2 are maximum certified hop independent and maximum hop independent set of H ′,
respectively. Thus, αch(H

′) = a and αh(H
′) = a+m = b.

Remark 1. The standard independence and certified hop independence parameters are
incomparable.

To see this, consider the graph G below.

a

b

c

d

e

f

g

h

i

j

k

l
m

G :

Figure 6: Graph G with α(G) < αch(G)

Let C = {a, b, c, d, i, k, l,m}. Then C is a maximum certified hop independent set of
G. Thus, αch(G) = 8. Next, let C ′ = {a, e, g, h, j, k}. Then C ′ is a maximum independent
set of G. Hence, α(G) = 6.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (1) (2024), 435-444 442

On the other hand, consider the graph H below.

a

b c

d e

f g

h

i j

k

H :

Figure 7: Graph H with αch(H) < α(H)

Let O1 = {a, b, c, f, g, h, j, k}. Then O1 is a maximum independent set of H. Thus,
α(H) = 8. Next, let O2 = {c, d, i, j}. Then O2 is a maximum certified hop independent
set of H. Therefore, αch(H) = 4.

Theorem 6. Let G and H be non-trivial graphs such that G and H have no complete
subgraphs of order |V (G)| − 1 and |V (H)| − 1, respectively. Then L ⊆ V (G + H) is
a certified hop independent set of G + H if and only if L satisfies one of the following
conditions:

(i) L = L ∩ V (G) = LG is clique in G.

(ii) L = L ∩ V (H) = LH is clique in H.

(iii) L = LG ∪ LH , where LG and LH are cliques in G and H, respectively.

Proof. Let L be a certified hop independent set of G+H and let LG = L ∩ V (G) and
LH = L ∩ V (H). If LH = ∅, then L = LG. Let x, y ∈ LG. Then

dG+H(x, y) = dG(x, y) ̸= 2.

This means that dG(x, y) = 1. Thus, LG is a clique in G. Similarly, if LG = ∅, then
LH = L ∩ V (H) is a clique in H. Suppose that LG ̸= ∅ and LH ̸= ∅. Since L is a hop
independent, LG and LH are clique in G and H, respectively.

Conversely, suppose that (i) holds. Then dG(a, b) = 1 = dG+H(a, b) for every
a, b ∈ L = LG. This means that L is a hop independent set of G + H. Since H is
non-trivial, there exist at least two vertices u, v ∈ V (H) such that u, v ∈ NG+H(a) and
u, v ∈ NG+H(b). Hence, L is a certified hop independent set of G + H. Similarly, when
(ii) holds, the assertion follows. Now, suppose that (iii) holds. Then L is a hop indepen-
dent set of G +H. Since G and H have no complete subgraphs of order |V (G)| − 1 and
|V (H)| − 1, respectively, clearly, L is a certified hop independent set of G+H.



REFERENCES 443

Corollary 4. Let G and H be non-trivial graphs such that G and H have no complete
subgraphs of order |V (G)| − 1 and |V (H)| − 1, respectively. Then

αch(G+H) = ω(G) + ω(H).

Proof. Let L be a maximum certified hop independent set of G+H. Then by Theoorem
6, L = LG ∪ LH , where LG and LH are cliques in G and H, respectively. It follows that
|LG| ≤ ω(G) and |LH | ≤ ω(H). Hence,

αch(G+H) = |L| = |LG|+ |LH | ≤ ω(G) + ω(H).

On the other hand, suppose that L = LG ∪ LH , where LG and LH are maximum
cliques in G and H, respectively. Then by Theorem 6, L is a certified hop independent
set of G+H. Thus, αch(G+H) ≥ |L| = ω(G) + ω(H). Consequently,

αch(G+H) = ω(G) + ω(H).

4. Conclusion

The concept of certified hop independence in graphs has been introduced and investi-
gated in this study. Its relationship with hop independence parameter has been presented.
Some bounds with respect to the order of a graph and exact values of parameters of some
special graphs have been determined. Moreover, characterizations of certified hop inde-
pendent sets in some graphs have been used to determine the exact values of parameters of
some graphs. Some graphs that were not considered in this study could be an interesting
topic to consider for further investigation of the concept. In addition, researchers may
consider the complexity, algorithm, and real life application of the concept.

Acknowledgements

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

References

[1] J. Hassan and S. Canoy Jr. Hop independent hop domination in graphs. Eur. J. Pure
Appl. Math., 15(2):1783–1796, 2022.

[2] J. Hassan, S. Canoy Jr., and A. Aradais. Hop independent sets in graphs. Eur. J.
Pure Appl. Math., 15(2):467–477, 2022.



REFERENCES 444

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

[4] J. Manditong, J. Hassan, LS Laja, AA. Laja, NHM. Mohammad, and SU. Kamdon.
Conneted outer-hop independent dominating sets in graphs under some binary opera-
tions. Eur. J. Pure Appl. Math., 16(3):1817–1829, 2023.