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

Certified Vertex Cover of a Graph

Javier A. Hassan1,∗, Maria Andrea O. Bonsocan2, Regimar A. Rasid1,
Amil-Shab S. Sappari1

1Mathematics and Sciences Department, College of Arts and Sciences, MSU Tawi-Tawi
College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines
2Department of Mathematics, Ateneo de Davao University, E. Jacinto Street, 8016 Davao
City, Philippines

Abstract. Let G be a graph. Then Q ⊆ V (G) is called a certified vertex cover of G if Q is a vertex
cover of G and every x ∈ Q, x has either zero or at least two neighbors in V (G) \Q. The certified
vertex cover number of G, denoted by βcer(G), is the minimum cardinality of a certified vertex
cover of G. In this paper, we investigate this newly defined concept on some special graphs and
on the join of two graphs. We characterize certified vertex cover in these graphs and subsequently
derive the simplified formulas for calculating the certified vertex cover number. Moreover, we
present some bounds and properties of certified vertex cover.

2020 Mathematics Subject Classifications: 05C69

Key Words and Phrases: Certified set, vertex cover, certified vertex covering set, certified
vertex cover number

1. Introduction

Vertex cover of a graph is an important concept in graph theory. A vertex cover of
a graph is a subset of vertices that covers all the edges in the graph. In other words,
every edge in the graph is incident to at least one vertex in the vertex cover. The concept
of vertex covering set has practical applications in various fields, such as network design,
optimization, and resource allocation. The size of the smallest vertex cover is called the
vertex cover number of the graph. Finding the minimum vertex cover or the vertex cover
number of a graph is an important problem in graph theory. In practical scenarios, finding
a minimum vertex cover helps in minimizing costs or maximizing efficiency. Researchers
had studied vertex cover parameter and its variants on different types of graphs (see
[1, 12, 13]).

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v17i2.5157

Email addresses: javierhassan@msutawi-tawi.edu.ph (J. A. Hassan)
mariaandrea.bonsocan@g.msuiit.edu.ph (M. A. Bonsocan)
regimarrasid@msutawi-tawi.edu.ph (R. A. Rasid)
amilshabsappari@msutawi-tawi.edu.ph (A. S. Sappari)

https://www.ejpam.com 1038 © 2023 EJPAM All rights reserved.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1039

Recently, V. Bilar et al. [1] introduced and investigated another variant of a vertex
cover called vertex cover hop domination. Let G be a graph. Then a subset C of a
vertex-set of G is called a vertex cover hop dominating if C is both a vertex cover and
a hop dominating of G. The vertex cover hop domination number of G, denoted by
γvch(G), is the minimum cardinality among all vertex cover hop dominating sets in G.
They have determined its relations with other parameters in graph theory such as vertex
cover, hop domination parameter. Moreover, they have characterized the vertex cover hop
dominating sets in some special graphs, join, and corona of two graphs, and obtained the
exact values or bounds of the parameter of these graphs. Some studies related to vertex
cover hop domination can be found in [2–11].

In this study, we initiate the study of certified vertex cover of a graph. We do believe,
this parameter and its results would lead to another interesting studies and applications
in the future. Further, this study would serve as reference to future researchers who will
study on concept or problem related to vertex cover of a graph.

2. Terminology and Notation

Let G = (V (G), E(G)) be a simple and undirected graph. Then S ⊆ V (G) is called
a vertex cover of G if every edge in G is incident to some vertex in S. The minimum
cardinality of a vertex cover of G, denoted by β(G), is called the vertex cover number of
G.

A set Q ⊆ V (G) is called a certified set of G if every vertex x ∈ Q, x has either zero
or at least two neighbors in V (G) \Q.

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

3. Results

We begin this section by introducing the concept of certified vertex cover of a graph.

Definition 1. Let G be a graph. Then Q ⊆ V (G) is called a certified vertex cover of G
if Q is a vertex cover of G and every x ∈ Q, x has either zero or at least two neighbors in
V (G) \ Q. The certified vertex cover number of G, denoted by βcer(G), is the minimum
cardinality of a certified vertex cover of G.

Example 1. Consider the graph G below.

Let Q = {u4, u5, u6, u7}. Then vertex u4 has three neighbors outside Q and vertices
u5, u6 and u7 have zero neighbor outside Q. It follows that Q is a certified vertex cover
of G. Observe that every edge of G is incident to some vertex in Q. Thus, Q is a vertex
cover of G, showing that Q is a certified vertex cover of G. Moreover, it can be verified
that βcer(G) = 4.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1040

u3

u4

u2 u5

u1

G :

u6

u7

Figure 1: Graph G with βcer(G) = 4

Proposition 1. Let G be a graph. Then

(i) β(G) ≤ βcer(G);

(ii) 1 ≤ βcer(G) ≤ |V (G)|;

(iii) a certified set of G may not be a vertex cover of G;

(iv) a vertex cover of G may not be a certified set of G; and

(v) if Q ⊆ V (G) is both certified and minimum vertex cover of G, then Q is a minimum
certified vertex cover of G and βcer(G) = |Q|.

Proof. (i) Let G be a graph and let Q be a minimum certified vertex cover of G. Then
Q is vertex cover of G. Since β(G) is the smallest cardinality of a vertex cover of G, it
follows that β(G) ≤ |Q| = βcer(G).

(ii) Since β(G) ≥ 1 for any graph G, βcer(G) ≥ 1 by (i). Clearly, βcer(G) ≤ |V (G)|.
Therefore,

1 ≤ βcer(G) ≤ |V (G)|.

(iii) Consider again the graph G below:

u3

u4

u2 u5

u1

G :

u6

u7



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1041

Let Q = {u4, u5}. Then u4 and u5 have three and two neighbors in V (G) \Q, respec-
tively. It follows that Q is a certified set of G. However, Q is not a vertex cover of G since
edge u6u7 is not incident to either u4 or u5. Hence, the assertion follows.

(iv) Consider again the graph G in (iii) and let S = {u4, u5, u6}. Then every edge of
G is incident to some elements of S, showing that S is a vertex cover of G. Now, observe
that vertex u5 and u6 have only one neighbor u7 outside S. It follows that S is not a
certified set of G. Hence, (iv) holds.

(v) Let Q be both certified and minimum vertex cover of G. Suppose that Q is not
a minimum certified vertex cover of G. Then there exists T ⊂ V (G) such that T is a
certified vertex cover and |Q| > |T |. Note that T is a vertex cover of G, a contradiction
to the fact Q is a minimum vertex cover of G. Therefore, Q is a minimum certified vertex
cove of G, and so βcer(G) = |Q|.

Lemma 1. Let n be a positive integer and let Q be a certified vertex cover of Pn, where
V (Pn) = {v1, v2, ..., vn}. Then Q = V (Pn) if and only if one of the following holds:

(i) vi, vj ∈ Q where dPn(vi, vj) = 1 for some i, j ∈ {1, 2, . . . , n}.

(ii) v1 ∈ Q.

(iii) vn ∈ Q.

Proof. Suppose that Q is a certified vertex cover of Pn. IfQ = V (Pn) = {v1, v2, . . . , vn},
then (i),(ii) and (iii) follow.

Conversely, suppose that (i) holds. That is, vi, vj ∈ Q such that dPn(vi, vj) = 1 for
some i, j ∈ {1, 2, . . . , n}. Assume that i < j. If j = n, then vi has only one neighbor vi−1

in V (Pn)\Q. Since Q is a certified set, vi−1 must be in Q. If vi−1 is in Q, then applying
the same argument, vi−2 must also be in Q. Continuing this process, all other vertices in
V (Pn)\Q must be in Q. Hence, Q = V (Pn).

Suppose that j ̸= n. Since dPn(vi, vj) = 1, both vi and vj have only one neighbor
vi−1 and vj+1 in V (Pn)\Q, respectively. Applying the same argument, all other vertices
in V (Pn)\Q must also be in Q. Thus, Q = V (Pn). Similarly, the same result follows when
i > j.

Now, suppose that (ii) holds, that is, v1 ∈ Q. Observe that v1 has only one neighbor
in V (Pn) \Q, which is v2. Since Q is a certified set in Pn, v2 must be in Q. However, v2
has only one neighbor in V (Pn) \Q, which is v3. Since Q is a certified set in Pn, v3 must
also be in Q. Continuing this process, all other vertices in V (Pn)\Q must be included as
elements of Q. Therefore, Q = V (Pn). Similarly, the assertion follows when (iii) holds.

The following Lemma can be proved similarly.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1042

Lemma 2. Let n be a positive integer and let Q be a certified vertex cover of Cn, where
V (Cn) = {v1, v2, . . . , vn}. Then Q = V (Cn) if and only if vi, vj ∈ Q such that

dCn(vi, vj) = 1.

Theorem 1. Let n be a positive integer. Then βcer(Pn) =

{
n , n = 1 or even⌊
n
2

⌋
, otherwise.

Proof. Let V (Pn) = {v1, v2, . . . , vn}. Clearly, βcer(P1) = 1, βcer(P2) = 2 and
βcer(P4) = 4. Suppose that n ≥ 6 and even. Let Q be a certified vertex cover of Pn.
If v1, vn ∈ Q or vi, vj ∈ Q, where dPn(vi, vj) = 1, then Q = V (Pn) by Lemma 1, and the
proof is complete.

Now, suppose that v1, vn /∈ Q and dPn(vs, vt) ≥ 2 for every s, t ∈ {2, . . . , n–1}.
Since Q is a vertex cover of Pn, it follows that either {v2, v4, . . . , vn−2, vn−1} ⊆ Q or
{v2, v4, . . . , vn−2, vn} ⊆ Q . By Lemma 1, either of this case, we have Q = V (Pn). There-
fore, βcer(Pn) = n for all n ≥ 6 and even.

Next, suppose that n ≥ 5 and odd. Let S = {v2, v4, . . . , vn−1}. Then S is a minimum
vertex cover of Pn. Clearly, S is a certified set of Pn. Therefore, βcer(Pn) = |S| =

⌊
n
2

⌋
since n is odd.

Theorem 2. Let n be a positive integer. Then βcer(Cn) =

{
n , if n is odd
n
2 , if n is even.

Proof. Let n be a positive integer and V(Cn) = {v1, v2, . . . , vn}. Let n = 3. Then
β(C3) = 2, and so βcer(C3) ≥ 2 by Proposition 1. Suppose that βcer(C3) = 2. Then
there exists vi ∈ V (C3)\N for some i ∈ {1, 2, 3}, where N is a certified vertex cover of
C3. Assume that i = 1. Then both v2, v3 ∈ N have only one neighbor v1 outside N , a
contradiction. Similarly, when i = 2 or i = 3. Therefore, βcer(C3) = 3.

Now, suppose that n ≥ 5 and odd. Let Q be a certified vertex cover of Cn and let
vi, vj ∈ Q for some i, j ∈ {1, 2, . . . , n}. If dCn(vi, vj) = 1, then by Lemma 2, Q = V (Cn)
and we are done. Now, since Q is a vertex cover, dCn(vi, vj) < 3. Thus, dCn(vi, vj) = 2.
WLOG, assume that v1 ∈ Q. Then v1, v3, . . . , vn−2 ∈ Q. Since Q is vertex cover, ei-
ther vn−1 or vn must be in Q. If vn−1 ∈ Q, then v1, v3, . . . , vn−2, vn−1 ∈ Q. Since
dCn(vn−1, vn−2) = 1, it follows that Q = V (Cn) by Lemma 2. Similarly, when vn ∈ Q,
then Q = V (Cn). Therefore, βcer(Cn) = n for all n ≥ 3 and odd.

Next, suppose that n ≥ 4 and even. Let Q1 = {v1, v3, . . . , vn−1}. Then Q1 is a
minimum vertex cover of Cn. Clearly, Q1 is a certified set of Cn. Since n is even, it follows
that βcer(Cn) = |Q1| = n

2 for all n ≥ 4 and even.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1043

Theorem 3. Let m be a positive integer. Then N is a certified vertex cover of Km if and
only if N = V (Km).

Proof. Let N be a certified vertex cover of Km. Then N is a vertex cover of Km by
definition. Thus, βcer(Km) ≥ m−1 since β(G) ≤ βcer(G) for any graph G. If βcer(G) = m,
then N = V (Km), and we are done. Suppose that βcer(Km) = m− 1. Then there exists a
unique x ∈ V (Km) such that x /∈ N . However, each vertex in N has only one neighbor x
outside N , which is a contradiction to the fact that N is a certified set of Km. Therefore,
N = V (Km) for all m ≥ 1.

The converse is clear.

Corollary 1. Let m be a positive integer. Then βcer(Km) = m.

Theorem 4. Let G and H be two graphs with no trivial components. Then Q ⊆ V (G+H)
is a certified vertex cover of G +H if and only if Q = QG ∪ QH and satisfies one of the
following conditions:

(i) QG = V (G) and QH is a certified vertex cover of H.

(ii) QH = V (H) and QG is a certified vertex cover of G.

Proof. Suppose that Q is a certified vertex cover of G +H. If Q = V (G +H), then
we are done. Assume that Q ̸= V (G + H). Since Q is a vertex cover of G + H, either
QG = V (G) and QH ̸= V (H) or QG ̸= V (G) and QH = V (H). Suppose that QG = V (G)
and QH ̸= V (H). Since Q is a certified vertex cover of G + H, QH must be a certified
vertex cover of H. Thus, (i) holds. Similarly, when QG ̸= V (G) and QH = V (H), then
(ii) holds.

Conversely, suppose that (i) holds. Let x ∈ Q. Then either x ∈ QG = V (G) or
x ∈ QH ⊆ V (H). Assume that x ∈ QG = V (G). Since H has no trivial components
and QH ⊆ V (H) is a certified set in H, it follows that x has either zero or at least two
neighbors in V (H) \ QH . Since x is arbitrary, Q is a certified set in G + H. Since QH

is a vertex cover of H, Q = V (G) ∪ QH is a vertex cover of G + H. Therefore, Q is a
certified vertex cover of G + H. Similarly, the assertion follows when x ∈ QH ⊆ V (H).
The assertion also follows, when (ii) holds.

Corollary 2. Let G and H be graphs with no trivial components. Then

βcer(G+H) = min{|V (G)|+ βcer(H), |V (H)|+ βcer(G)}.

Theorem 5. Let G be a trivial graph and H be a graph with no trivial components. Then
Q ⊆ V (G +H) is a certified vertex cover of G +H if and only if Q = QG ∪ QH , where
QG = V (G) and QH is a certified vertex cover of H.



J. A. Hassan et al. / Eur. J. Pure Appl. Math, 17 (2) (2024), 1038-1045 1044

Proof. Suppose that Q is a certified vertex cover of G +H. If Q = V (G +H), then
we are done. Assume that Q ̸= V (G + H). Since Q is a vertex cover of G + H, either
QG = V (G) and QH ̸= V (H) or QG ̸= V (G) and QH = V (H). Since G is trivial and Q is
a certified set in G+H, QG ̸= V (G) and QH = V (H) is not possible. Hence, QG = V (G)
and Q ̸= V (H). Since Q is a certified vertex cover of G+H, QH must be a certified vertex
cover of H.

Conversely, suppose that Q = QG ∪ QH , where QG = V (G) and QH is a certified
vertex cover of H. Let y ∈ Q. Then either y ∈ QG = V (G) or y ∈ QH ⊆ V (H). Assume
that y ∈ QG = V (G). Since H has no trivial components and QH ⊆ V (H) is a certified
set in H, it follows that y has either zero or at least two neighbors in V (H) \QH . Since
y is arbitrary, Q is a certified set in G + H. Since QH is a vertex cover of H, it follows
that Q = V (G) ∪QH is a certified vertex cover of G+H. Similarly, the assertion follows
when y ∈ QH ⊆ V (H).

Corollary 3. Let G be a trivial graph and H be a graph with no trivial components. Then

βcer(G+H) = βcer(H) + 1

In particular, each of the following holds:

(i) βcer(Fn) =

{
n+ 1 , if n ≥ 2 and even⌊
n
2

⌋
+ 1 , if n ≥ 3 and odd.

(ii) βcer(Wn) =

{
n+ 1 , if n is odd
n
2 + 1 , if n is even.

4. Conclusion

The concept of certified vertex cover has been introduced and initially investigated in
this study. Defining the concept introduces a new idea in graph theory. The minimum
cardinality of a certified vertex cover of some graphs has been determined in this study.
Additionally, characterizations of vertex covering sets of certain graphs have aided in
determining the exact values of parameters of some graphs. Exploring graphs that haven’t
been addressed in this study could prove to be interesting, offering a fresh perspective on
the concept. Investigating these unexplored graphs might reveal new insights and provide
a deeper understanding of the concept. Moreover, interested researchers may study the
complexity and algorithms of solving the certified vertex cover number of a graph.

Acknowledgements

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



REFERENCES 1045

Also, the authors would like to thank the referees for their invaluable comments and
suggestions that led to the improvement 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] 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.

[3] J. Hassan and S. Canoy. Connected grundy hop dominating sequences in graphs.,.
Eur. J. Pure Appl. Math., 16(2):1212–1227, 2023.

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

[5] J. Hassan and S. Canoy Jr. Grundy total hop dominating sequences in graphs. Eur.
J. Pure Appl. Math., 16(4):2597–2612, 2023.

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

[7] A.Y. Isahac, J. Hassan, LS. Laja, and HB. Copel. Outer-convex hop domination in
graphs under some binary operations. Eur. J. Pure Appl. Math., 16(4):2035–2048,
2023.

[8] S. Canoy Jr. and J. Hassan. Weakly convex hop dominating sets in graphs. Eur. J.
Pure Appl. Math., 15(4):1783–1796, 2022.

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

[10] J. Manditong, A. Tapeing, J. Hassan, A.R. Bakkang, N.H. Mohammad, and S.U.
Kamdon. Some properties of zero forcing hop dominating sets in a graph. Eur. J.
Pure Appl. Math., 17(1):324–337, 2024.

[11] J. Mohamad and H. Rara. On resolving hop domination in graphs. Eur. J. Pure
Appl. Math., 14(1):324–337, 2021.

[12] T. Sitthiwirattham. Vertex covering and independent number on difference graphs.
International Journal of Pure and Applied Mathematics., 77(4):543–547, 2012.

[13] J. Uy. Revisiting the vertex cover of graphs. Applied Mathematical Sciences.,
115(9):5707–5714, 2015.