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

2-Path Geodetic Vertex Cover of Graphs
Aziz B. Tapeing1,2, Sergio R. Canoy, Jr.1,2,∗

1 Department of Mathematics and Statistics, College of Science and Mathematics,
MSU-Iligan Institute of Technology, Iligan City, Philippines
2 Center of Mathematical and Theoretical Physical Sciences - PRISM, MSU-Iligan Institute
of Technology, Iligan City, Philippines

Abstract. A vertex cover S ⊆ V (G) is called a 2-path geodetic vertex cover of G if for every
v ∈ V (G) \ S, there exist vertices u,w ∈ S such that dG(u,w) = 2 and v ∈ IG(u,w). The 2-path
geodetic vertex covering number of G, denoted β2pg(G), is the minimum cardinality of a 2-path
geodetic vertex covering of G.
In this paper, we show that given two positive integers a and b such that 2 ≤ a ≤ b, there exists
a connected graph G such that β(G) = a and β2pg = b. As a consequence, the difference between
the 2-path geodetic vertex covering number and the classical vertex covering number of a graph
can be made arbitrarily large. We characterize graphs with small and large values of the 2-path
geodetic vertex covering number. Furthermore, we provide necessary and sufficient conditions for
the 2-path geodetic vertex covers in certain graph operations. The exact values of 2-path geodetic
vertex cover numbers of these graphs are also determined.
2020 Mathematics Subject Classifications: 05C69
Key Words and Phrases: Geodetic, vertex cover, vertex cover number

1. Introduction

The concept of vertex covering in graphs has been extensively studied (see, for in-
stance, [1], [2], [3], [4]). As noted by Angel and Amutha [5], this parameter has practical
applications in network security. In particular, their study highlights that in computer
networks, minimizing the vertex cover number provides an optimal strategy for network
defense. Toregas et al. [6] further demonstrated that this concept is utilized in determining
the optimal placement of emergency facilities within telecommunication networks.

Despite its significance, the vertex cover problem is classified as an NP-hard optimiza-
tion problem. Specifically, Karp [7] established its NP-completeness by leveraging the
known result that the clique problem is NP-complete. For cubic and planar graphs, the

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v18i4.6904
Email addresses: Aziz.tapeing@g.msuiit.edu.ph (A. B. Tapeing),
sergio.canoy@g.msuiit.edu.ph (S. R. Canoy Jr.)

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



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 2 of 14

vertex covering problem is still NP-complete. For complete details, one may refer to [8]
and [9].

The problem of determining bounds and exact values for the vertex cover number of
specific classes of graphs has been extensively studied (see [10], [11]). In recent years,
several variations of the vertex cover concepts have been introduced and investigated (see
[5], [12], [13], [14], [15], [1], [16], [17], and [18]).

Motivated by the aforementioned studies, we introduce and initiate the study 2-path
geodetic vertex cover of a graph. This new parameter naturally extends two existing
concepts: 2-path geodetic set and vertex cover of a graph. For some related works on the
concept of geodetic and 2-path closure absorbing set, readers may see [19], [20], [21], and
[22].

2. Terminologies and Notations

Let G = (V (G), E(G)) be a simple undirected graph. The open neighborhood of a
vertex v of G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} (the set consisting of all the
neighbors of v), while its closed neighborhood is the set NG[v] = NG(v) ∪ {v}. The open
neighborhood of a set S ⊆ V (G) is the set NG(S) = ∪v∈SNG(v) and its closed neighborhood
is the set NG[S] = S∪NG(S). Any v ∈ V (G) with |NG(v)| = 0 is called an isolated vertex.
Vertex v is a leaf or an endvertex if |NG(v)| = 1. A vertex w of G is a support vertex if
wv ∈ E(G) for some leaf v in G. A vertex w is an extreme vertex in G if the induced
subgraph ⟨NG(v)⟩ of NG(v) is complete. The sets I(G), L(G), S(G) and Ext(G) denote
the sets containing of all the isolated vertices, leaves, support vertices, and extreme vertices
in G, respectively.

A subset A of V (G) is an independent set if for every pair of distinct vertices in G
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.

A set S ⊆ V (G) is a dominating set in G if NG[S] = V (G). It is a 2-dominating set
if |NG(v) ∩ S| ≥ 2 for every v ∈ V (G) \ S. The domination number (resp. 2-domination
number) of G, denoted γ(G) (resp. γ2(G)) is the minimum cardinality of a dominating
(resp. 2-dominating) set in G. Any dominating set (2-dominating set) with cardinality
γ(G) (resp. γ2(G)) is called a γ-set (resp. γ2-set) in G.

A subset S ⊆ V (G) is called a geodetic set of a graph G if for every vertex v ∈
V (G), there exist vertices u,w ∈ S such that v ∈ IG[u,w], where IG[u,w] denotes the
set consisting of u,w, and all vertices that lie on some shortest path between u and w
in G. This shortest path connecting u and w is called a u-w geodesic. A set S ⊆ V (G)
is a 2-path geodetic or 2-path closure absorbing set in G if for each x ∈ V (G) \ S, there
exist p, q ∈ S such that x ∈ IG(p, q) and dG(p, q) = 2, where IG(p, q) = IG[p, q] \ {p, q}.
The smallest cardinality among all 2-path geodetic sets in G, denoted g2p(G), is called the
2-path geodetic number of G.

A 2-path geodetic set S is 2-path geodetic 2-dominating if S is 2-dominating in G.
The smallest cardinality of a 2-path geodetic 2-dominating set in G, denoted γ2pg2(G), is



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 3 of 14

called the 2-path geodetic 2-domination number of G. Any 2-path geodetic 2-dominating
set with cardinality γ2pg2(G) is referred to as a γ2pg2-set.

A subset U of vertices of a graph G is called a vertex cover of G if for every e = uv ∈
E(G), u ∈ U or v ∈ U . The minimum cardinality of a vertex cover of G, denoted β(G),
is the vertex cover number of G. Any vertex cover of G with cardinality β(G) is called a
β-set.

A set S ⊆ V (G) is called a 2-path geodetic vertex cover of G if it is both a vertex cover
and a 2-path geodetic set in G. The smallest cardinality of a 2-path geodetic vertex cover
of G, denoted β2pg(G), is called the 2-path geodetic vertex cover number of G. Any 2-path
geodetic vertex cover of G with cardinality β2pg(G) is called a β2pg-set.

Consider the graph G in Figure 1. Let S = {a, c, f}. Since every edge of G is incident
to some vertex in S, it follows that S is a vertex cover of G. Moreover, b, d ∈ IG(a, c) and
e ∈ IG(c, f). Thus, S is a 2-path geodetic vertex cover of G. Since there exists no 2-path
geodetic vertex cover with cardinality less than 3, it follows that β2pg(G) = |S| = 3.

a b

cd e

f

Figure 1: A graph G with β2pg(G) = 3

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 shadow graph D2(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).

Readers are referred to [23] for other basic definitions that are not given here.

3. Results

Since V (G) is a 2-path geodetic vertex cover of G, it follows that any graph G admits
a 2-path geodetic vertex cover.

Remark 1. A 2-path geodetic set need not be a vertex cover and a vertex cover need not
be a 2-path geodetic set.

To see this, consider graph G in Figure 2. Let S1 = {v1, v3, w1, w3} and S2 = {v2, w2}.
Clearly, S1 and S2 are 2-path geodetic set and vertex cover of G, respectively. Since
v2w2 ∈ E(G) and v2, w2 /∈ S1, it follows that S1 is not a vertex cover of G. By definition,
S2 is not a 2-path geodetic set in G. It can easily be verified that g2p(G) = |S1| = 4 and



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 4 of 14

β(G) = 2.

................................................................................................................ ................................................................................................................ ....................................

................................................................................................................ ................................................................................................................ ....................................

.........

........

........

........

........

........

........

........

........

...
....................................

....................................

v1 v2 v3

w1 w2 w3

G

Figure 2: Graph G with β(G) = 2 and g2p(G) = 4

Remark 2. Let G be a graph and let S be a vertex cover of G. Then V (G) \ S is an
independent set. Moreover, α(G) + β(G) = |V (G)|.

Proposition 1. Let G be any graph and let S be a 2-path geodetic set in G. Then each
of the following holds:

(i) Ext(G) ∪ I(G) ⊆ S and |Ext(G)|+ |I(G)| ≤ g2p(G).

(ii) S is a 2-dominating set and γ2(G) ≤ g2p(G).

Proof. Clearly, every 2-path geodetic set is a geodetic set. Now, since every geodetic set
in a graph contains all the extreme and isolated vertices, it follows that Ext(G)∪I(G) ⊆ S
and the given inequality in (i) holds.

Next, let v ∈ V (G) \S. Since S is a 2-path geodetic set in G, there exist p, q ∈ S such
that dG(p, q) = 2 and v ∈ IG(p, q). It follows that S is a 2-dominating set in G. Thus,
γ2(G) ≤ g2(G).

The next result is a direct consequence of Proposition 1(i).

Corollary 1. Let n be a positive integer. Then β2pg(Kn) = β2pg(Kn) = n.

Theorem 1. Let G1, G2, .., Gk, where k ≥ 1, be the components of G. Then S is a 2-path
geodetic vertex cover of G if and only if S =

∪
j∈[k] Sj, where Sj is a 2-path geodetic vertex

cover of Gj for every j ∈ [k] = {1, 2, .., k}. Moreover,

β2pg(G) =
∑
j∈[k]

β2pg(Gj).

Proof. Suppose S is a 2-path geodetic vertex cover of G. Let Sj = S ∩ V (Gj) for each
j ∈ [k] = {1, 2, .., k}. Then S = ∪j∈[k]Sj . Since S is a 2-path geodetic set in G, Sj ̸= ∅
for all j ∈ [k]. Next, let j ∈ [k] and let ab ∈ E(Gj). Since S is a vertex cover in G, it
follows that a ∈ S or b ∈ S. Hence, a ∈ Sj or b ∈ Sj , showing that Sj is a vertex cover
of Gj . Now let v ∈ V (Gj) \ S. Since S is a 2-path geodetic set in G, there exist y, z ∈ S
such that dG(y, z) = 2 and x ∈ IG(y, z). This implies that there exist y, z ∈ Sj such that



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 5 of 14

dGj (y, z) = 2 and x ∈ IGj (y, z). Therefore Sj is a 2-path geodetic vertex cover in Gj . In
particular, if S is a β2pg-set in G, then

β2pg(G) = |S| =
∑
j∈[k]

|Sj | ≥
∑
j∈[k]

β2pg(Gj).

For the converse, suppose S = ∪j∈[k]Sj , where Sj is a 2-path geodetic vertex cover of Gj for
all j ∈ [k] = {1, 2, . . . , k}. Let pq ∈ E(G). Then there exists j ∈ [k] such that pq ∈ E(Gj).
Since Sj is a vertex cover of Gj , we have p ∈ Sj or q ∈ Sj . It follows that p ∈ S or q ∈ S.
Let v ∈ V (G) \ S, and let t ∈ [k] such that v ∈ V (Gt) \ St. Since St is a 2-path geodetic
set in Gt, there exist u,w ∈ St such that dG(u,w) = 2 and v ∈ IGt(u,w) = IG(u,w).
Therefore S is a 2-path geodetic vertex cover of G. If each Sj is a β2pg-set in Gj , then

β2pg(G) ≤ |S| =
∑
j∈[k]

|Sj | =
∑
j∈[k]

β2pg(Gj).

This proves the assertion.

Theorem 2. Let G be a graph of order n. Then

max{β(G), g2p(G)} ≤ β2pg(G) ≤ n.

Moreover, the following statements hold.

(i) g2p(G) = β2pg(G) if and only if G has g2p-set which is also a vertex cover of G.

(ii) β(G) = β2pg(G) if and only if G has β-set which is also a 2-path geodetic set in G.

Proof. Clearly, β2pg(G) ≤ n. Since every 2-path geodetic vertex cover is both 2-path
geodetic and a vertex cover, we have max{β(G), g2p(G)} ≤ β2pg(G).

(i) Suppose that g2p(G) = β2pg(G). Let S be a β2pg-set in G. By assumption, S is a
g2p-set in G.

For the converse, suppose that G has a g2p-set S which is also a vertex cover of G.
Then S is a 2-path geodetic vertex cover of G. Hence, β2pg(G) ≤ |S| = g2p(G). By the
first part, it follows that β2pg(G) = g2p(G).

(ii) Suppose that β(G) = β2pg(G). Let S be a β2pg-set in G. By assumption, S is a
β-set in G.

Conversely, suppose that G has a β-set S which is also a 2-path geodetic set in G.
Then S is a 2-path geodetic vertex cover of G. Hence, β2pg(G) ≤ |S| = β(G). With the
first part, this implies that β2pg(G) = β(G).

Theorem 3. Let G be a graph of order n. Then

(i) β2pg(G) = 1 if and only if G = K1

(ii) β2pg(G) = 2 if and only if G ∈ {K2,K2,K2,n−2}



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 6 of 14

(iii) β2pg(G) = 3 if and only if G ∈ {K3,K3, P1 ∪ P2} or there exist distinct vertices
x, y, z ∈ V (G) such that V (G) \ {x, y, z} is an independent set and one of the
following conditions holds:

(a) ⟨{x, y, z}⟩ = K3 and for every v ∈ V (G)\{x, y, z}, it holds that |NG(v) ∩ {x, y, z}| ≥
2 or

(b) ⟨{x, y, z}⟩ = ⟨x⟩∪⟨{y, z}⟩ = P1∪P2 and for every v ∈ V (G)\{x, y, z}, we have
x, y ∈ NG(v) or x, z ∈ NG(v).

(c) ⟨{x, y, z}⟩ = P3 = [x, y, z] ̸= G and for every v ∈ V (G) \ {x, y, z}, it holds that
x, z ∈ NG(v) and NG(y) \ {x, y, z} ̸= ∅.

Proof. (i) Suppose that β2pg(G) = 1, say S = {v} is a β2pg-set in G. Since S is a
2-path geodetic set, V (G) = {v}, i.e, G = K1.

For the converse, suppose that G = K1. By Proposition 1, β2pg(G) = 1.

(ii) Suppoe β2pg(G) = 2, say S = {u, v} is a β2pg-set. If n = 2, then G ∈ {K2,K2}.
Suppose n ≥ 3. Let x ∈ V (G) \ S. Since S is a 2-path geodetic set, x ∈ IG(u, v) and
dG(u, v) = 2. Let G1 = ⟨{u, v}⟩ and G2 = ⟨V (G) \ S⟩. Then G1 = K2 and, by Remark 2,
G2 = Kn−2. Thus, G = K2 +Kn−2 = K2,n−2.

The converse is clear.

(iii) Suppose that β2pg(G) = 3. Let S = {x, y, z} be a β2pg-set in G. Then V (G) \ S
is an independent by Remark 2. Suppose |V (G)| = 3. Since β2pg(P3) = 2 and β2pg(K3) =
β2pg(K3) = β2pg(P1 ∪ P2) = 3, it follows that G ∈ {K3,K3, P1 ∪ P2}. Next, suppose that
|V (G)| ≥ 4. Then V (G) \ {x, y, z} ̸= ∅. Clearly, ⟨S⟩ ̸= K3 since any v ∈ V (S) \ S cannot
be in IG(S). Suppose now that ⟨S⟩ = K3 and let v ∈ V (G) \ S. Since S is a 2-path
geodetic set in G, it follows that |NG(v) ∩ S| ≥ 2. This proves (a). Suppose now that
⟨S⟩ = ⟨x⟩ ∪ ⟨{y, z}⟩ = P1 ∪ P2 and let v ∈ V (G) \ S. Since S is a 2-path geodetic set in
G, it follows that x, z ∈ NG(v) or x, y ∈ NG(v). This proves (b). Finally, suppose that
⟨{x, y, z}⟩ = [x, y, z] = P3 ̸= G. Let v ∈ V (G)\{x, y, z}. Since {x, y, z} is a 2-path geodetic
set, x, z ∈ NG(v). Suppose NG(y) \ S = ∅. Since y ∈ IG(x, z), it follows that {x, z} is a
2-path geodetic vertex cover of G, a contradiction to the assumption that β2pg(G) = 3.
Thus, there exists w ∈ NG(y) \ S, showing that (c) holds.

For the converse, suppose that V (G) \ S is independent. Assume first that G ∈
{K3,K3, P1 ∪ P2}. Then β2pg(G) = 3. Next, suppose that (a) holds. Let S = {x, y, z}
and let vw ∈ E(G). Since V (G) \ S is independent, it follows that v ∈ S or w ∈ S. Hence
S is a vertex cover of G. Let v ∈ V (G) \ S. Then, by (a), S is a 2-path geodetic set in
G. Therefore, S is a 2-path geodetic vertex cover and β2pg(G) = |S| = 3 by (ii). Suppose
that (b) holds. Let pq ∈ E(G). Again, since V (G) \ S is an independent set, p ∈ S or
q ∈ S. Let v ∈ V (G)\S. By (b), it follows that S is a 2-path geodetic set in G. Therefore,
S is a geodetic vertex cover in G. Again, by (ii), it follows that β2pg(G) = |S| = 3. Lastly,
suppose that (c) holds. Since V (G) \ S is independent, S is a vertex cover of G. Let
v ∈ V (G) \ S. Since x, z ∈ NG(v), it follows that v ∈ IG(x, z). Hence, S is a 2-path



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 7 of 14

geodetic set in G. Moreover, since NG(y) \ S ̸= ∅, G ̸= K2,n−2. Thus, by part (ii), we
must have β2pg(G) = 3.

Theorem 4. Let G be a graph of order n. Then β2pg(G) = n if and if G′ is complete for
every component G′ of G.

Proof. Suppose that β2pg(G) = n. Suppose further that there exists a component G′

of G which is not complete. Then there exist vertices p, q ∈ V (G′) such that dG(p, q) = 2.
Let x ∈ NG(p) ∩ NG(q). Then D = V (G′) \ {x} is a 2-path geodetic vertex cover of G′.
This implies that β2pg(G′) ≤ |V (G′)|− 1. By Theorem 1, β2pg(G) ≤ n− 1, a contradiction
to the assumption. Therefore, every component of G is complete.

For the converse, suppose that every component G′ of G is complete. By Corollary
1, β2pg(G

′) = |V (G′)| for every component G′ of G. Therefore, by Theorem1, we have
β2pg(G) = n.

Theorem 5. Let G be a graph of order n. Then β2pg(G) = n− 1 if and only if all but a
component H of G are complete and ⟨V (H) \ Ext(H)⟩ is complete.

Proof. Let G1, G2, · · · , Gk be the components of G. Suppose β2pg = n−1. By Theorem
1 and Theorem 4, there exists a component H = Gt of G which is not complete. Hence, by
Theorem 1 and the assumption, β2pg(H) = |V (H)| − 1 and β2pg(Gj) = |V (Gj)| for every
j ∈ {1, 2, · · · , t − 1, t + 1, · · · , k}. Let H∗ = ⟨V (H) \ Ext(H)⟩. Since H is connected, it
follows that H∗ is connected. Suppose H∗ = ⟨V (H) \ Ext(H)⟩ is not complete. Choose
any p, q ∈ V (H∗) such that dG(p, q) = dH(p, q) = 2. Since p, q /∈ Ext(H), each of them
has non-adjacent neighbors. This implies that S = V (H) \ {p, q} is a 2-path geodetic
vertex covering of H, a contradiction. Thus, H∗ is complete.

For the converse, suppose that Gj is complete for all j ∈ {1, 2, · · · , t− 1, t+ 1, · · · , k}
and that H = Gt is non-complete satisfying the property that H∗ = ⟨V (H) \ Ext(H)⟩ is
complete. Then β2pg(H) ≤ |V (H)| − 1 and β2pg(Gj) = |V (Gj)| for all j ∈ {1, 2, · · · , t −
1, t+1, · · · , k} by Theorem 4. Let D be a β2pg-set in H. Then Ext(H) ⊆ D by Proposition
1(i). If H∗ is the trivial graph, say H∗ = ⟨v⟩, then D = Ext(H). Hence, β2pg(H) = |D| =
|V (H)| − 1. Suppose H∗ is nontrivial. Since H∗ is connected (it contains an edge) and D
is a vertex cover , it follows that D ∩ V (H∗) ̸= ∅, i.e., D ̸= Ext(H). Suppose there exist
distinct vertices p, q ∈ V (H∗) \D. Then pq ∈ E(H) because H∗ is complete. This implies
that D is not a vertex covering of H, a contradiction. Thus, |D ∩ V (H∗)| = |V (H∗)| − 1.
Therefore, β2pg(H) = |D| = |V (H)| − 1. By Theorem 1, β2pg(G) = n− 1.

Theorem 6. Let G = Km1,m2,..,mk
, where 2 ≤ m1 ≤, ..,≤ mk. Then β2pg(G) =

∑k−1
j=1 mj .

Proof. Let S1, S2, ...Sk be the partite sets of G. Clearly,
k−1∪
i=1

Si is a 2-path geodetic

vertex cover of G. It follows that β2pg(G) ≤
k−1∑
j=1

mj . Next, let S be a β2pg-set of G. Since



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 8 of 14

G is not complete, it follows that S ̸= V (G). Let v ∈ V (G) \ S and let r ∈ {1, 2, . . . , k}
such that v ∈ Sr. Since vw ∈ E(G) for all w ∈

∪
i ̸=r

Si and S is a vertex cover of G, it

follows that
∪
j ̸=r

Si ⊆ S. Therefore,

k−1∑
j=1

mj ≤
∑
j ̸=r

mj ≤ |S| = β2pg(G).

This proves the assertion.

Observation 1. Let n be a positive integer. Then
(i) β2pg(Pn) = ⌈n+1

2 ⌉ for all n and
(ii) β2pg(Cn) = ⌈n2 ⌉ for all n ≥ 4.

We now give some realization results involving the parameters 2-path geodetic number,
vertex cover number, and 2-path geodetic vertex cover number.

Theorem 7. Given two positive integers a and b such that 3 ≤ a ≤ b, there exists a
connected graph G such that g2p(G) = a and β2pg(G) = b.

Proof. If a = b, then let G = K1,a. Clearly, g2p(G) = β2pg(G) = a.
Suppose now that a < b. Consider the graph G in Figure 3 with complete subgraphs

Ka−1 and Kb−a+1, where V (Ka−1) = {v1, . . . , va−1} and V (Kb−a+1) = {x1, . . . , xb−a+1}.
Let D = {v1, . . . , va−1, va}, Then D is g2p-set in G, implying that g2p(G) = a. Let
D0 be a β2pg-set in G. Then Ext(G) = {v1, v2, . . . va−2, va} ⊆ D0 by Proposition 1(i).
If va−1 /∈ D0, then V (Kb−a+1) ⊆ D0 because D0 is a vertex cover of G. Hence,
D0 = Ext(G) ∪ V (Kb−a+1). It follows that |D0| = (a − 1) + (b − a + 1) = b.
Suppose va−1 ∈ D0. Again, since D0 is a vertex cover of G, |V (Kb−a+1) ∩D0| = b− a.

Ka−1 Kb−a+1

va

x1

...

xb−a+1

va−1
G :

Figure 3: Graph G with g2p(G) = a < b = β2pg(G)

This implies that D0 = a+ (b− a) = b. Therefore, β2pg(G) = |D0| = b.
The next result is direct consequence of Theorem 7.

Corollary 2. Let n be a positive integer. Then there exists a connected graph G such that
β2pg(G) − g2p(G) = n. In other words, the difference β2pg(G) − g2p(G) can be increased
arbitrarily.



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 9 of 14

Theorem 8. Given two positive integers a and b such that 2 ≤ a ≤ b, there exists a
connected graph G such that β(G) = a and β2pg(G) = b.

Proof. If a = b, then consider the cycle G = C2a. Clearly, β(G) = β2pg(G) = ⌈2a2 ⌉ = a.
Next, suppose a < b. Consider the graph G in Figure 4 with the complete

graph Ka and the star K1,b−a as subgraphs, where V (Ka) = {v1, . . . , va−1, x} and
V (K1,b−a) = {va, x1, . . . , xb−a}. Let S1 be a β-set in G. If x ∈ S1, then |{v1, . . . , va−1} ∩
S1| = a−2 and va ∈ S1 because S1 is a β-set in G. If x /∈ S1, then S1 = {v1, . . . , va−1, va}.
In both cases, |S1| = a. Hence, β(G) = a. Now, let S2 be a β2pg-set in G. Then
{v1, . . . , va−1, x1, . . . , xb−a} ⊆ S2 by Proposition 1(i). Also, since S2 is a β2pg-set in G, we
have |{x, va} ∩ S2| = 1. Thus, β2pg(G) = |S2| = (a− 1) + (b− a) + 1 = b.

Ka

vax

x1

x2

x3
...
xb−a

G :

Figure 4: Graph G with β(G) = a < b = β2pg(G)

Therefore, the assertion holds.

The next result follows from Theorem 8.

Corollary 3. Let n be a positive integer. Then there exists a connected graph G such that
β2pg(G)−β(G) = n. In other words, the difference β2pg(G)−β(G) can be made arbitrarily
large.

If what follows, we denote by G1 and G2 the copies of graph G in the definition of the
shadow graph D2(G). Moreover, we denote by v′ the vertex in G2 corresponding to the
vertex v ∈ V (G1).

Theorem 9. Let G be a non-trivial connected graph. Then S ⊆ V (D2(G)) is a vertex
cover of D2(G) if and only if S = SG1 ∪ SG2 and satisfies the following conditions:

(i) S = SG1 ∪ SG2, where SG1 and SG2 are vertex covers of G1 and G2, respectively.

(ii) For each v ∈ V (G1)\SG1, it holds that w ∈ SG1 and w′ ∈ SG2 for every w ∈ NG1(v).

(iii) For each p′ ∈ V (G2)\SG2, it holds that q ∈ SG1 and q′ ∈ SG2 for every q′ ∈ NG2(p
′).

Proof. Suppose S is a vertex cover of D2(G). Then SG1 = S ∩ V (G1) and SG2 =
S ∩ V (G2) are vertex covers of G1 and G2, respectively, because S is a vertex cover of
D2(G). This shows that (i) holds. Now let v ∈ V (G1) \ SG1 and let w ∈ NG1(v). Since
SG1 is vertex cover of G1, it follows that w ∈ SG1 . Also, since vw′ ∈ E(D2(G)) and S is



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 10 of 14

a vertex cover of D2(G), we have w′ ∈ SG2 . This shows that (ii) holds. Similarly, (iii)
holds.

For the converse, suppose that S has the given form and satisfies (i), (ii), and (iii).
Let xy ∈ E(D2(G)) and consider the following cases:

Case 1. xy ∈ E(G1) ∪ E(G2).

If xy ∈ E(G1), then x ∈ SG1 or y ∈ SG1 because SG1 is a vertex cover of G1. Similarly,
x ∈ SG2 or y ∈ SG2 whenever xy ∈ E(G2).

Case 2. x ∈ V (G1) and y ∈ V (G2).

Let y = z′ where z ∈ V (G1). If x ∈ SG1 , then we are done. So suppose x ∈ V (G1)\SG1 .
Since z ∈ NG(x), it follows from (ii) that z′ ∈ SG2 . Thus, y ∈ S.

Therefore, S is a vertex cover of D2(G).

Theorem 10. Let G be a non-trivial connected graph. Then S ⊆ V (D2(G)) is a vertex
cover of D2(G) if and only if it is a 2-path geodetic vertex cover of D2(G).

Proof. Suppose S is a vertex cover of D2(G). Then S = SG1 ∪ SG2 and satisfies
properties (i), (ii), and (iii) of Theorem 9. Now let v ∈ D2(G) \ S. Suppose v ∈ V (G1) \
SG1 . Pick any w ∈ V (G1) ∩ NG1(v). Then w,w′ ∈ S by (ii). Clearly, dD2(G)(w,w

′) = 2
and v ∈ ID2(G)(w,w

′). If v ∈ V (G2) \ SG2 , say v = z′ where z ∈ V (G1), then we may
choose any x′ ∈ V (G2) ∩ NG2(z

′). By (iii), x, x′ ∈ S. Moreover, dD2(G)(x, x
′) = 2 and

v ∈ ID2(G)(x, x
′). Thus, S is a 2-path geodetic vertex cover of D2(G).

The converse is clear.

Corollary 4. Let G be a non-trivial connected graph. Then

β2pg(D2(G)) = β(D2(G)) = 2β(G).

Proof. Let S1 be a β-set in G1 and let S2 = {v′ ∈ V (G2) : v ∈ S1}. Then S2 is a
β-set in G2. Moreover, S = S1 ∪ S2 is a vertex cover of D2(G) by Theorem 9. Thus, by
Theorem 10,

β2pg(D2(G)) = β(D2(G)) ≤ |S| = |S1|+ |S2| = 2β(G).

Next, let S0 be a β-set of D2(G). Then S0 = SG1 ∪SG2 where SG1 and SG2 are vertex
covers of G1 and G2, respectively, by Theorem 9. By Theorem 10, we have

β2pg(D2(G)) = β(D2(G)) = |S0| = |SG1 |+ |SG2 | ≥ 2β(G).

This establishes the desired equality.

Theorem 11. Let G be a non-complete graph and let m be a positive integer. Then
S ⊆ V (Km +G) is a 2-path geodetic vertex cover of Km +G if and only if S = (V (Km) \



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 11 of 14

{v}) ∪ V (G) for some v ∈ V (Km) or S = V (Km) ∪ SG, where SG is a 2-path geodetic
vertex cover of G.

Proof. Suppose S is a 2-path geodetic vertex cover of Km+G. Suppose V (Km)\S ̸= ∅,
say v ∈ V (Km) \ S. Since S is a vertex cover of Km + G, it follows that V (G) ⊆ S and
|V (Km) \S| = 1. Hence, S = (V (Km) \ {v})∪V (G). Next, suppose that V (Km) \S = ∅.
Let SG = S ∩ V (G). Then S = V (Km) ∪ SG. Since S is a vertex cover of Km + G, it
follows that SG is vertex cover of G. Let w ∈ V (G) \ SG. Since S is a 2-path geodetic set
in Km+G, there exist y, z ∈ V (Km+G) such that w ∈ IKm+G(y, z) and dKm+G(y, z) = 2.
This implies that y, z ∈ V (G), w ∈ IG(y, z) and dG(y, z) = 2. Hence, SG is a 2-path
geodetic vertex cover of G.

For the converse, suppose first S = (V (Km) \ {v})∪ V (G) for some v ∈ V (Km). Then
clearly, S is a 2-path geodetic vertex cover of Km+G. Next, suppose that S = V (Km)∪SG,
where SG is a 2-path geodetic vertex cover of G. Let ab ∈ E(Km+G). If ab /∈ E(G), then
a ∈ V (Km) or b ∈ V (Km). Suppose ab ∈ E(G). Since SG is a vertex cover of G, a ∈ SG

or b ∈ SG. Hence, in both cases, a ∈ S or b ∈ S. Let w ∈ V (Km + G) \ S. Then w ∈
V (G) \ SG. This implies that there exist p, q ∈ SG such that dKm+G(p, q) = dG(p, q) = 2
and w ∈ IG(p, q). Since IG(p, q) = IKm+G(p, q), it follows that S is a 2-path geodetic
vertex cover of Km +G.

The next results are consequence of Theorem 11.

Corollary 5. Let G be a non-complete graph and let m be a positive integer. Then

β2pg(Km +G) = min{(m− 1) + |V (G)| , β2pg(G) +m}.

Corollary 6. Let G be a non-complete graph. Then

β2pg(K1 +G) = min{|V (G)|, β2pg(G) + 1}.

Moreover,

(i) β2pg(K1,n) = β2pg(K1 +Kn) = n for all n ≥ 2;

(ii) β2pg(Fn) = β2pg(K1 + Pn) = ⌈n+1
2 ⌉+ 1 for all n ≥ 3;

(iii) β2pg(Wn) = β2pg(K1 + Cn) = ⌈n2 ⌉+ 1 for all n ≥ 4; and

(iv) β2pg(K1 +
k∪

j=1

Kmj ) =
k∑

j=1

mj for k ≥ 2.

Theorem 12. Let G and H be non-complete graphs. Then S ⊆ V (G + H) is a 2-path
geodetic vertex cover of G+H if and only if one of the following statements holds:

(i) S = V (G) ∪ SH where SH is a vertex cover of H.

(ii) S = SG ∪ V (H) where SG is a vertex cover of G.



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 12 of 14

Proof. Suppose S is a 2-path geodetic vertex cover of G +H. Suppose V (G) \ S ̸= ∅
and V (H) \ S ̸= ∅. Let x ∈ V (G) \ S and y ∈ V (H) \ S. Then xy ∈ E(G + H) and
x, y /∈ S. This is not possible because S is a vertex cover of G+H. Hence, V (G) \ S = ∅
or V (H) \ S = ∅. Suppose V (G) \ S = ∅. Then V (G) ⊆ S. Let SH = S ∩ V (H) and let
ab ∈ E(H). Since S is a vertex cover of G +H, it follows that a ∈ SH or b ∈ SH . This
implies that SH is a vertex cover of H, showing that (i) holds. Similarly, (ii) holds if
V (H) \ S = ∅.

For the converse, suppose that (i) holds. Let st ∈ E(G+H). If s ∈ V (G) or t ∈ V (G),
then st is incident to a vertex in S. Suppose st ∈ E(H). Since SH is a vertex cover of H,
s ∈ SH or t ∈ SH . It follows that S is a vertex cover of G +H. Let z ∈ V (G +H) \ S.
Then z ∈ V (H) \ SH . Choose any p, q ∈ V (G) such that dG(p, q) ̸= 1. Then p, q ∈ S,
dG+H(p, q) = 2, and z ∈ IG+H(p, q). Therefore, S is a 2-path geodetic vertex cover of
G+H. We obtain the same conclusion if (ii) holds.

The next result follows from Theorem 12.

Corollary 7. Let G and H be non-complete graphs on m and n vertices, respectively.
Then

β2pg(G+H) = min{m+ β(H), n+ β(G)}.

In particular, each of the following hold.

(i) β2pg(Km,n) = min{m,n} for m,n ≥ 2.

(ii) β2pg(Pm + Pn) = min{m+ ⌊n2 ⌋, n+ ⌊m2 ⌋} for m,n ≥ 3.

(iii) β2pg(Cm + Cn) = min{m+ ⌈n2 ⌉, n+ ⌈m2 ⌉} for m,n ≥ 4.

4. Conclusion

In this paper, the concept of 2-path geodetic vertex covering of a graph has been
introduced and initially studied. It was shown that the difference β2pg(G) − β(G) can
be increased arbitrarily. Graphs which attain small and large values of the parameter
have been characterized. Also, 2-path geodetic vertex coverings in the shadow graph and
the join of graphs have been characterized and, subsequently, values of the parameter for
these graphs have been determined. This newly defined variant of vertex covering can
also be investigated for other classes of graphs. Moreover, while the vertex cover problem
is NP-complete, it remains to show whether or not the 2-path geodetic vertex covering
problem is also NP-complete.

Acknowledgements

The authors would like to thank the referees for the comments and suggestions they
gave the authors. The authors are also grateful to the Department of Science and Tech-
nology - Accelerated Science and Technology Human Resource Development Program



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 13 of 14

(DOST-ASTHRDP)-Philippines and the MSU-Iligan Institute of Technology, Iligan City
for funding this research.

References

[1] M. Henning and A. Yeo. Identifying vertex covers in graphs. The Electric Journal in
Mathematics,, 19(4):1038–1045., 2012.

[2] S. Canoy Jr and R. Artes Jr. Vertex and edge covering numbers of a graph: Revisited.
Congressus Numerantium, 167:65, 2004.

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

[4] J. Uy and V. Abregana. Revisiting the vertex cover of graphs. Applied Mathematical
Sciences, 9:5707 – 5714, 2015.

[5] D. Angel and A. Amutha. Vertex covering and strong covering of flower like network
structures. Procedia Computer Science, 87:164–171, 2016.

[6] C. Toregas, , R. Swain, C. Revelle, and L. Bercman. The location of emergency
service facilities. Journal of the Operations Research Society of America, 19(6), 1971.

[7] R.M. Karp. Reducibility among combinatorial problems, complexity of computer
computations. Plenum Press, New York, pages 85–103, 1972.

[8] M.R. Garey and D.S. Johnson. The rectilinear steiner tree problem is np-complete.
SIAM Journal on Applied Mathematics, 32:826–834, 1977.

[9] M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified npcomplete problems.
Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pages 47–
63, 1974.

[10] B. Behsaz, P. Hatami, and E.S. Mahmoodian. On minimum vertex cover of general-
ized petersen graphs. Australian Journal of Combinatorics, 40:253–264, 2008.

[11] J. Uy. Vertex cover of graphs. Journal of Research in Science and Engineering,
1:49–53, 2003.

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

[13] J. Hassan, M. A. Bonsocan, R. Rasid, and A. Sappari. Certified vertex cover of a
graph. ur. J. Pure Appl. Math., 17(2):1038–1045, 2024.

[14] J. Hassan, S. Canoy Jr, A. Gamorez, E. Ahmad, and A. Sappari. 2-vertex covering
of a graph. European Journal of Pure & Applied Mathematics, 18(2), 2025.

[15] S. Canoy Jr, M.A. Bonsocan, J. Hassan, A.M. Mahistrado, and V. Bilar. Super vertex
cover of a graph. European Journal of Pure & Applied Mathematics, 18(1), 2025.

[16] M. Marathe, R. Ravi, and C. P. Rangan. Generalized vertex covering in interval
graphs. Discrete Applied Mathematics, 39:87–93, 1992.

[17] P. Pushpam and C. Suseendran. Secure vertex cover of a graph. Discrete Mathematics,
Algorithms and Applications, 9(2), 2017.

[18] L. Sathikala, K. K. Basari, and K. Subramanian. Connected and total vertex covering
in graphs. Turkish Journal of Computer and Mathematics Education, 12(2):2180–
2185, 2021.



A. B. Tapeing, S. R. Canoy / Eur. J. Pure Appl. Math, 18 (4) (2025), 6904 14 of 14

[19] G. Cagaanan and S. Canoy Jr. Bounds for the geodetic number of the cartesian
product of graphs. Utilitas Mathematica, 79:91–98, 2009.

[20] G. Cagaanan and Jr. S. Canoy. On the geodetic and hull numbers of some graphs.
ASIA PACIFIC JOURNAL OF SOCIAL INNOVATION, 19(1), 2005.

[21] F. Jamil, I. Aniversario, and S. Canoy Jr. On closed and upper closed geodetic
numbers of graphs. Ars Combinatoria, 84:191–204, 2007.

[22] S. Canoy Jr, G. Cagaanan, and S. Gervacio. Convexity, geodetic, and hull numbers
of the join of graphs. 2006.

[23] F. Buckley and F. Harary. Distance in graphs. Addison-Wesley, Redwood City, 1990.