EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 2, Article Number 6063 ISSN 1307-5543 – ejpam.com Published by New York Business Global 2-Vertex Covering of a Graph Javier A. Hassan1,2,∗, Sergio R. Canoy, Jr.3,4, Anabel Gamorez5, Eman C. Ahmad5, An-Nadzwie 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, College of Science, Korea University, Seoul, South Korea 3Department of Mathematics and Statistics, College of Science and Mathematics, MSU-Iligan Institute of Technology, Iligan City, Philippines 4Center of Mathematical and Theoretical Physical Sciences, PRISM, MSU-Iligan Institute of Technology, Iligan City, Philippines 5Department of Mathematics and Statistics, College of Science and Mathematics, Western Mindanao State University, Zamboanga City, Philippines Abstract. In this paper, we initiate the study on 2-vertex covering of a graph. We characterize the 2-vertex covering sets in some special graphs, join and corona of two graphs, and we derive some bounds or formulas of the said parameter of each of these graphs. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Vertex cover, 2-domination, 2-vertex covering set, 2-vertex cover number 1. Introduction Vertex cover of a graph is one the well-studied parameters in the theory of graphs. In optimization, the parameter can be used to model some real-world problems and in the elimination of repetitive DNA sequences for synthetic biology [1]. The parameter, as pointed out by Angel and Toregas et al. in [2] and [3], respectively, can also serve to model safety, defense strategy, and emergency facility location problems. It is well-known that the vertex cover problem is an NP-hard optimization problem. Karp in [4] used the NP -completeness of the clique problem to show that the vertex cover problem is NP - complete. NP -completeness of the vertex problem was also investigated by Garey et al. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i2.6063 Email addresses: javierhassan@msutawi-tawi.edu.ph (J. Hassan) sergio.canoy@g.msuiit.edu.ph (S. Canoy, Jr.) anabel.gamorez@wmsu.edu.ph (A. Gamorez) ahmad.eman@wmsu.edu.ph (E. Ahmad) annadzwiesappari@msutawi-tawi.edu.ph (A. Sappari) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 2 of 11 in [5] and [6]. Other studies on vertex cover and its variations can be found in [7], [8], [9], [10], [11], [12], and [13]. Vertex cover is closely related to the concept of domination. In fact, for a non-trivial connected graph, a vertex cover is a dominating set. Undoubtedly, a vertex cover can be made a dominating set in any graph by incorporating a domination-related concept in its definition. In this way, a variant of vertex cover emerges (see, for example, [8], [9], [10], [11], and [12]). Using the concept of 2-domination, we introduce the parameter called 2-vertex cover of a graph. As used to model a protection strategy in a network, the 2-vertex covering ensures that every node or vertex outside the cover has at least two neighbors coming from the covering. For studies that deal with 2-domination and its variants, readers may consider [14], [15],[16], [17], and [18]. 2. Terminologies and Notations The open neighborhood of a vertex v of a simple undirected graph G is the set NG(v) = {u ∈ V (G) : uv ∈ E(G)} and 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). A vertex v ∈ V (G) is an isolated vertex if |NG(v)| = 0. The set containing all the isolated vertices in G will be denoted by I(G). A vertex v is a leaf or an endvertex if |NG(v)| = 1. The set L(G) will denote the set consisting of all the leaves in 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)}. 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. A subset A of V (G) is independent 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. A set S ⊆ V (G) is a dominating set in G if NG[S] = V (G). It is a 2-dominating set if for every v ∈ V (G) \ S, |NG(v) ∩ S| ≥ 2, i.e., v has at least two neighbors in S. The domination number (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). A subset S of vertices of a graph G is called a vertex cover of G if for every edge e = uv ∈ E(G), either u ∈ S or v ∈ S. The minimum cardinality of a vertex cover of G is the vertex cover number of G and is denoted by β(G). Any vertex cover of G with cardinality β(G) is called a β-set. A set S ⊆ V (G) is a 2-vertex cover (or covering) of G if S is both a vertex cover and a 2-dominating set in G. The 2-vertex covering number of G, denoted by β2(G), is the minimum cardinality of a 2-vertex covering of G. Any 2-vertex covering of G with cardinality β2(G) is called a β2-set. J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 3 of 11 Readers are referred to [19] for other basic definitions that are not given here. 3. Main results Theorem 1. Let G1, G2, . . . , Gk be the components of G. Then β2(G) = ∑k j=1 β2(Gj). Proof. Let S be a β2-set in G. For each j ∈ [k] = {1, 2, · · · , k}, let Sj = S ∩ V (Gj). Then S = ∪k j=1Sj . Since S is a vertex cover of G, it follows that Sj is a vertex cover of Gj for each j ∈ [k]. Now, let j ∈ [k] and let v ∈ V (Gj) \ Sj . Since S is a 2-dominating set in G, we have |NG(v) ∩ S| ≥ 2. It follows that |NGj (v) ∩ Sj | ≥ 2. Therefore, Sj is a 2-vertex cover of Gj for each j ∈ [k]. Thus, β2(G) = |S| = | ∪k j=1 Sj | = k∑ j=1 |Sj | ≥ k∑ j=1 β2(Gj). For each j ∈ [k], let Dj be a β2-set in Gj . Clearly, D = ∪k j=1Dj is a 2-vertex cover of G. Hence, β2(G) ≤ |D| = | ∪k j=1 Dj | = k∑ j=1 |Dj | = k∑ j=1 β2(Gj). This proves the assertion. Theorem 2. Let G be a graph on n vertices. Then max{γ2(G), β(G)} ≤ β2(G) ≤ n. Moreover, each of the following holds: (i) If G has vertex v with |NG(v)| ≥ 2, then β2(G) ≤ n − 1. In particular, if G is a connected graph and n ≥ 3, then β2(G) ≤ n− 1. (ii) β2(G) = 1 if and only if G = K1. (iii) β2(G) = 2 if and only if G ∈ {K2,K2,K2 +H,K2 +H} for some graph H of order n− 2. (iv) β2(G) = n if and only if G′ ∈ {K1,K2} for every component G′ of G. Proof. Since every 2-vertex covering of G is both a vertex cover and a 2-dominating set in G, it follows that max{γ2(G), β(G)} ≤ β2(G). Clealy, β2(G) ≤ n. (i) Suppose G has vertex v with |NG(v)| ≥ 2. Then clealy, S = V (G) \ {v} is a 2-vertex cover of G. Hence, β2(G) ≤ |S| = n − 1. If G is connected and n ≥ 3, then there exists w ∈ V (G) with |NG(w)| ≥ 2. Therefore, β2(G) ≤ n− 1. (ii) Suppose β2(G) = 1, and let S = {v} be a β2-set of G. Since S is a 2-dominating set, there can be no vertex outside S. Hence, G = K1. J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 4 of 11 The converse is clear. (iii) Suppose β2(G) = 2, say S = {x, y} is a β2-set of G. Suppose first that xy ∈ E(G). If n = 2, then G = K2. Suppose n ≥ 2 and z ∈ V (G) \ S. Since S is a 2-dominating set in G, we have z ∈ NG(x) ∩NG(y). This implies that G = ⟨{x, y}⟩+H = K2 +H, where H = ⟨V (G) \ S⟩ is a graph of order n − 2. Next, suppose xy /∈ E(G). If n = 2, then G = K2 by (ii) and Theorem 1. Suppose n ≥ 3. Following an earlier argument, we have V (G)\S ⊆ NG(x)∩NG(y). Therefore, G = ⟨{x, y}⟩+H = K2+H, where H = ⟨V (G)\S⟩ is a graph of order n− 2. Accordingly, G ∈ {K2,K2,K2 +H,K2 +H} for some graph H of order n− 2. The converse is clear. (iv) Suppose β2(G) = n. From (i), it follows that |NG(v)| ≤ 1 for every v ∈ V (G). This implies that G′ ∈ {K1,K2} for every component G′ of G. For the converse, suppose that G′ ∈ {K1,K2} for every component G′ of G. From (ii) and (iii), and by Theorem 1, it follows that β2(G) = n. Theorem 3. Let G be a graph on n vertices such that |NG(v)| ≥ 2 for some vertex v ∈ V (G). Then β2(G) = n−1 if and only if for every pair of non-adjacent vertices p and q of G, it holds that p, q ∈ L(G) ∪ I(G). Proof. Suppose β2(G) = n − 1. Suppose, for a contradiction, that there exist non- adjacent vertices p and q such that p, q /∈ L(G)∪I(G). Then |NG(p)| ≥ 2 and |NG(q)| ≥ 2. It follows that S = V (G) \ {p, q} is a 2-vertex covering of G, implying that β(G) ≤ |S| = n− 2, a contradiction to our assumption. Therefore, G satisfies the given property. For the converse, suppose that G satisfies the property and let S′ be a β2-set in G. Since |NG(v)| ≥ 2 for some vertex v ∈ V (G), it follows from Theorem 2 that β2(G) = |S′| ≤ n − 1. Suppose for a contradiction that β2(G) ≤ n − 2. Then there exist distinct vertices x, y ∈ V (G)\S′. Since S′ is a vertex cover of G, we have xy /∈ E(G). This implies that x, y ∈ L(G) ∪ I(G) by the assumption. Therefore, S is not a 2-dominating set in G, a contradiction. Accordingly, β2(G) = |S′| = n− 1. The next result is immediate from Theorem 3. Corollary 1. Let n be a positive integer such that n ≥ 3. Then (i) β2(Kn) = n− 1, and (ii) β2(K1,n−1) = n− 1. Theorem 4. Let n be a positive integer. Then β2(Pn) = {⌈ n 2 ⌉ , if n is odd n 2 + 1 , if n is even J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 5 of 11 Proof. From (ii) and (iii) of Theorem 2, we have β2(P1) = 1 = 1+1 2 and β2(P2) = 2 = 2 2 + 1. Let S be a β2-set on Pn. Suppose first that n is odd and n ≥ 3, say n = 2r + 1 where r ≥ 1. Let Pn = [a1, a2, . . . , a2r, a2r+1]. Since S is a 2-dominating set, we have a1, a2r+1 ∈ S. Again, since S is a β2-set of Pn, it follows that S = {a1, a3, . . . , a2r−1, a2r+1}. Hence, β2(Pn) = |S| = n+ 1 2 = ⌈n 2 ⌉ . Next, suppose n is even and n ≥ 4, say n = 2t where t ≥ 2. Let Pn = [a1, a2, . . . , a2r−1, a2r]. Since S is 2-dominating, a1, a2r ∈ S. Again, since S is a β2-set of Pn, S = {a1, a3, . . . , a2r−1}∪ {a2r+1}. Hence, β2(Pn) = |S| = n 2 + 1. Theorem 5. Let n be a positive integer where n ≥ 3. Then β2(Cn) = {⌈ n 2 ⌉ , if n is odd n 2 , if n is even Proof. Let D be a β2-set on Pn. Suppose n is odd. Clearly, β2(C3) = 2 = 1+1 2 . So sup- pose that n ≥ 5, say n = 2r + 1 where r ≥ 2. Let Cn = [b1, b2, . . . , b2r, b2r+1, b1]. We may assume that b1 ∈ D. Since D is a β2-set of Cn, it follows that D = {b1, b3, . . . , b2r−1, b2r+1}. Hence, β2(Cn) = |D| = n+ 1 2 = ⌈n 2 ⌉ . Now, suppose that n is even and n ≥ 4, say n = 2m form ≥ 2. Let Cn = [b1, b2, . . . , b2m−1, b2m, b1]. Again, we may assume that b1 ∈ D. SinceD is a β2-set of Cn, we haveD = {b1, b3, . . . , b2m−1}. Hence, β2(Pn) = |D| = n 2 . Theorem 6. Let G = Km1,m2,··· ,mk be a complete k-partite graph with 2 ≤ m1 ≤ m2 ≤ · · · ≤ mk. Then β2(G) = ∑ i∈[k]\{k} mi where [k] = {1, 2, · · · , k}. Proof. Let S1, S2, · · · , Sk be the partite sets of G and let S be a β2-set of G. Suppose v ∈ V (G) \ S. Then there exists j ∈ [k] = {1, 2, · · · , k} such that v ∈ Sj . Since S is a vertex cover of G, it follows that ∪i∈[k]\{j}Si ⊆ S. Moreover, since V (G) \ Sj is a 2-vertex cover of G and S is a β2-set of G, S = V (G) \ Sj . Again, because S is a β2-set of G, we must have j = k. Therefore, β2(G) = |S| = ∑ i∈[k]\{k}mi. The next result follows from Theorem 6. J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 6 of 11 Corollary 2. Let m and n be positive integers such that 2 ≤ m ≤ n. For the complete bipartite Km,n, we have β2(Km,n) = m. Remark 1. Let G be a graph and let S be a 2-vertex cover of G. Then L(G)∪ I(G) ⊆ S. Theorem 7. Let a and b be positive integers such that 3 ≤ a ≤ b. Then there exists a connected graph G such that β(G) = a and β2(G) = b. Proof. If a = b, then consider G = Ka+1. Then β(G) = a and, by Corollary 1(i), β2(G) = a. Next, suppose a < b and letm = b−a. Let G be the graph obtained fromKa+1 by adding m pendant edges v1x1, v1x2, . . . , v1xm, where V (Ka+1) = {v1, v2, · · · , va, va+1} (see Figure 2). Clearly, S1 = {v1, v2, · · · , va} is a vertex cover of G. Hence, β(G) ≤ |S1| = a. Let S be a β-set in G. If v1 /∈ S, then {v2, v3, · · · , va+1} ⊆ S since S is a vertex cover of G. Again, since S is a vertex cover of G, it follows that {x1, x2, · · · , xm} ⊆ S. Thus, S = {x1, x2, · · · , xm, v2, v3, · · · , va+1}. Consequently, β(G) = |S| = m+ a = b− a+ a = b, which is not possible. Thus, v1 ∈ S. Suppose |(V (Ka+1) \ {v1}) ∩ S| < a− 1. Then there exist r, t ∈ {2, 3, · · · , a + 1} such that vr, vt /∈ S. This, however, is not possible because vrvt ∈ E(G) and S is a vertex cover. Therefore, |(V (Ka+1)\{v1})∩S| = a−1. Therefore, since S is a β-set in G, β(G) = |S| = a. Let D be a β2-set in G. By Remark 1, {x1, x2, · · · , xm} ⊆ S. Now suppose v1 /∈ S. Since D is a vertex cover of G, it follows that {v2, v3, · · · , va+1} ⊆ D. Hence, D = {x1, x2, · · · , xm, v2, v3, · · · , va+1}. This implies that β2(G) = |D| = m + a = b. Suppose v1 ∈ D. Since D is a vertex cover of G, |V (Ka+1) \D| ≤ 1. The assumption that D is a β2-set in G forces |V (Ka+1) \D| = 1. Therefore, β2(G) = |D| = m+ a = b. v1 va+1vav8v7 v6 v5 v4 v3 v2 x1 xm xm−1 x3 x2 ... ... Therefore, the assertion holds. The next result is a consequence of Theorem 7. Corollary 3. Let n be a positive integer. Then there exists a connected graph G such that β2(G) − β(G) = n. In other words, the difference β2(G) − β(G) can be made arbitrarily large. Theorem 8. Let H be a non-trivial graph and let G = K1+H, where K1 = ⟨{v}⟩. Then a set S ⊆ V (G) is a 2-vertex cover of G+H if and only if S = V (H) or S = {v}∪DH∪I(H) where DH is a vertex cover of H such that DH ∩ I(G) = ∅. J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 7 of 11 Proof. Suppose S is a 2-vertex cover of G. Suppose v ∈ S and let w ∈ I(H). Since NG(w) ∩ S = {v} and S is 2-dominating set in G, w ∈ S. Thus, I(H) ⊆ S. Let DH = [V (H)\ I(H)]∩S. Since S is a vertex cover of G, DH is a vertex cover of H. Thus, (i) holds. If v /∈ S, then S = V (H) because vp ∈ E(G) for all p ∈ V (H) and S is a vertex cover of G. This implies that (ii) holds. For the converse, suppose that (i) holds. Clearly, S is a vertex cover of G. Let x ∈ V (G) \ S. Then x ∈ V (H) \ (DH ∪ I(G)). Since x /∈ I(G), xq ∈ E(H) for some q ∈ V (H). Since DH is a vertex cover of H, q ∈ DH . It follows that v, q ∈ NG(x) ∩ S. Hence, S is a 2-dominating set in G. Therefore, S is a 2-vertex cover of G. If (ii) holds, then S = V (H) is a 2-vertex cover of G because H is non-trivial. Lemma 1. Let G be a graph of order n and let S be a β-set of G. Then each of the following holds: (i) S ∩ I(G) = ∅. (ii) n = β(G) + |I(G)|+ |(V (G) \ I(G)) \ S|. (iii) If G is not the empty graph, then |(V (G) \ I(G)) \ S| ≥ 1. Hence, n = β(G) + |I(G)|+ |(V (G) \ I(G)) \ S| ≥ β(G) + |I(G)|+ 1. Proof. (i) Since a vertex cover only ensures that every edge is incident to a vertex inside the cover, S being a β-set of G implies that S ∩ I(G) = ∅. Hence, (i) holds. (ii) Since V (G) = S ∪ I(G) ∪ [V (G) \ I(G)) \ S], (i) implies that n = β(G) + |I(G)| + |(V (G) \ I(G)) \ S|. (iii) Suppose G ̸= Kn. Then S ̸= ∅ and β(G) = |S| ≤ n − 1. It follows that |(V (G) \ I(G)) \ S| ≥ 1. Therefore, n = β(G) + |I(G)|+ |(V (G) \ I(G)) \ S| ≥ β(G) + |I(G)|+ 1. Corollary 4. Let H be a non-trivial graph of order n and G = K1+H. Then each of the following holds: (i) If H ̸= Kn, then β2(G) = β(H) + |I(H)| + 1. Moreover, if H is connected, then β2(G) = β(H) + 1. (ii) If H = Kn, then β2(G) = n. Proof. (i) Suppose H ̸= Kn. Then V (H) \ I(H) ̸= ∅. Let DH be a β-set of H. Then DH ∩ I(H) = ∅. Let S = {v} ∪DH ∪ I(H). Then S is a 2-vertex cover of G by Theorem 8. It follows that β2(G) ≤ |S| = β(H) + |I(H)|+ 1. Next, suppose S0 is a β2-set of G. If S0 satisfies (ii) of Theorem 8, then S0 = {v} ∪ DH ∪ I(H) where DH is a vertex cover of H such that DH ∩ I(G) = ∅. Hence, β2(G) = J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 8 of 11 |S0| ≥ β(H) + |I(H)| + 1. Suppose S0 = V (H). Then β2(G) = |S0| = n. By Lemma 1, β2(G) ≥ β(H) + |I(H)|+ 1. Therefore, β2(G) = β(H) + |I(H)|+ 1. (ii) Suppose H = Kn. Then |I(H)| = n and DH = ∅ is the only vertex cover of H. Hence, by Theorem 8, S = V (H) is a β2-set of G. Thus, β2(G) = n. Theorem 9. Let G and H be non-trivial graphs. Then S ⊆ V (G + H) is a 2-vertex covering of G+H if and only if S = SG∪SH and satisfies one of the following conditions: (i) SG = V (G) and SH is a vertex cover of H. (ii) SH = V (H) and SG is a vertex cover of G. Proof. Suppose S is a 2-vertex cover of G+H. Let SG = S∩V (G) and SH = S∩V (H). Then S = SG ∪ SH . Suppose SG ̸= V (G) and SH ̸= V (H). Pick any x ∈ V (G) \ SG and p ∈ V (H) \ SH . Since xp ∈ E(G+H), it follows that S is not a vertex cover of G+H, a contradiction. Thus, SG = V (G) or SH = V (H). Suppose SG = V (G) and let st ∈ E(H). Since S is a vertex cover of G + H, s ∈ SH or t ∈ SH . Hence, SH is a vertex cover of H, showing that (i) holds. Similarly, SG is a vertex cover of G whenever SH = V (H), showing that (ii) holds. For the converse, suppose that S = SG ∪ SH and (i) holds. Let pq ∈ E(G + H). If p ∈ V (G) or q ∈ V (G), then p ∈ S or q ∈ S. Suppose pq ∈ E(H). Since SH is a vertex cover of H, p ∈ SH ⊂ S or q ∈ SH ⊂ S. This implies that S is a vertex cover of G +H. Now let z ∈ V (G+H) \ S. Since SG = V (G), z ∈ V (H) \ SH . The assumption that G is non-trivial assures that |NG+H(z) ∩ S| ≥ |NG+H(z) ∩ SG| = |SG| ≥ 2. Therefore, S is a 2-vertex covering of G. The same conclusion is true for S if (ii) holds. The next result is a consequence of Theorem 9 Corollary 5. Let G and H be non-trivial graphs of orders m and n, respectively. Then β2(G+H) = min{m+ β(H), n+ β(G)}. Theorem 10. Let G be a non-trivial connected graph and let H be any graph. Then S ⊆ V (G ◦ H) is a 2-vertex cover of G ◦ H if and only if D = Q ∪ (∪v∈V (G)Rv) and satisfies the following conditions: (i) Q is a vertex cover of G. (ii) I(Hw) ⊆ Rw and Rw \ I(Hw) is a vertex cover of Hv for each w ∈ Q. (iii) Sv = V (Hv) for each v ∈ V (G) \Q. Proof. Assume that S is a 2-vertex cover of G ◦H. Let Q = D ∩ V (G) and let Rv = D∩V (Hv) for each v ∈ V (G). Clearly, D = Q∪(∪v∈V (G)Rv). Let pq ∈ E(G) ⊂ E(G◦H). The assumption that D is a vertex cover of G ◦ H implies that p ∈ Q or b ∈ Q. This shows that Q is a vertex cover of G. This, in turn, shows that (i) holds. Let w ∈ Q. J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 9 of 11 Since D is a 2-dominating set, it follows that I(Hw) ⊆ Rw. Let st ∈ E(Hw). Then s, t ∈ V (Hw) \ I(Hw). Since D is a vertex cover of G ◦ H), s ∈ Rw or t ∈ Rw. Hence, s ∈ Rw \ I(Hw) or t ∈ Rw \ I(Hw). This implies that Rw \ I(Hw) is a vertex cover of Hw. Thus, (ii) holds. Next, let v /∈ Q and let q ∈ V (Hv). Since D is a vertex cover of G ◦H and vq ∈ E(G ◦H), q ∈ Rv. Since v was an arbitrary vertex of Hv, it follows that Rv = V (Hv). This shows that (iii) also holds. For the converse, suppose that D is as described and satisfies (i), (ii), and (iii). Let vw ∈ E(G ◦ H). If v, w ∈ V (G), then v ∈ Q or v ∈ Q by (i). Suppose v ∈ V (G) and w ∈ V (Hv). If v ∈ Q, then vw is incident to v ∈ D. Suppose v /∈ Q. Then Rv = V (Hv) by (iii). Hence, w ∈ Sv and vw is incident to w ∈ D. Next, suppose that that v, w ∈ V (Hz) for some z ∈ V (G). If z /∈ Q, then Rz = V (Hz). This implies that v, w ∈ Rz ⊂ D. Suppose that z ∈ Q. Since vw ∈ E(G ◦ H), v, w ∈ V (Hz) \ I(Hz). By (ii), Rz \ I(Hz) is a vertex cover of Hz. It follows that v ∈ Rz \ I(Hz) or w ∈ Rz \ I(Hz). Therefore, D is a vertex cover of G ◦H. Finally, let x ∈ V (G ◦H) \D and let v ∈ V (G) such that x ∈ V (v + Hv). If x = v, then v /∈ Q. By (iii), Rv = V (Hv). Since G is a non-trivial connected graph and Q is a vertex cover of G, it follows that NG(v)∩Q ̸= ∅. Choose any u ∈ NG(v) ∩ Q and s ∈ Rv. Then u, s ∈ NG◦H(v) ∩D. Suppose x ∈ V (Hv) \ Rv. Then x /∈ I(Hv) because x /∈ D. Also, from (iii), it follows that v ∈ Q (otherwise, Rv = V (Hv) contrary to the fact that x ∈ V (Hv) \ Rv). Hence, from (ii), Rv \ I(G) is a vertex cover of Hv. This implies that NHv(x) ∩ (Rv \ I(G)) ̸= ∅. Since v ∈ NG◦H(x), it follows that |NG◦H(x) ∩ D| ≥ |NHv(x) ∩ (Rv \ I(G))| + 1 ≥ 2. This shows that D is a 2-dominating set in G ◦H. Therefore, D is a 2-vertex cover of G ◦H. Corollary 6. Let G be a non-trivial connected graph of order m and let H be any graph of order n. Then β2(G ◦H) = mn+ (β(H)− n+ |I(H)|+ 1)β(G). In particular, if H is a non-trivial connected graph, then β2(G ◦H) = mn+ (β(H)− n+ 1)β(G). Proof. Let Q be a β-set in G, Dv a β-set in Hv and Rv = Dv ∪ I(Hv) for each v ∈ Q, and let Sv = V (Hv) for each v ∈ V (G) \ Q. Then D = Q ∪ (∪v∈V (G)Rv) is a 2-vertex cover of G ◦H by Theorem 10. It follows that β2(G ◦H) ≤ |D| = |Q|+ ∑ v∈Q |Rv|+ ∑ v∈V (G)\Q |Rv| = β(G) + β(G)[β(H) + |I(H)|+ n(m− β(G)) = mn+ (β(H)− n+ |I(H)|+ 1)β(G). On the other hand, let D0 be a β2-set in G ◦ H. Then D0 = X ∪ (∪v∈V (G)Tv) and satisfies properties (i), (ii), and (iii) of Theorem 10. Hence, X is a vertex cover of G J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 10 of 11 by (i), Tv = Sv ∪ I(Hv), where Sv is a vertex cover of Hv, for each v ∈ X by (ii), and Tv = V (Hv) for each v ∈ V (G) \X by (iii). Thus, β2(G ◦H) = |D0| = |X|+ ∑ v∈X |Tv|+ ∑ v∈V (G)\X |Tv| ≥ |X|+ ∑ v∈X (β(H) + |I(H)|) + ∑ v∈V (G)\X n = |X|+ |X|(β(H) + |I(H)|) + (m− |X|)n = mn+ (β(H) + |I(H)| − n+ 1)|X| ≥ mn+ (β(H) + |I(H)| − n+ 1)β(G). This establishes the desired equality. If H is a non-trivial connected graph, then |I(H)| = 0. Hence, the additional assertion holds. 4. Conclusion The parameter 2-vertex cover, a variant of vertex cover, had been introduced and initially studied. This newly defined concept incorporates the concept of 2-domination in a graph. We gave bounds on the parameter, obtained the value of the parameter for some well-known classes of graphs, and characterized graphs that attain specific values such as 1, 2, n − 1, and n, where n is the order of the graph. We also characterized the 2-vertex covering in the join and corona of two graphs and determined their 2-vertex cover numbers. We also showed that the difference between 2-vertex cover number and vertex cover number can be made arbitrarily large. The new parameter can be studied for other classes of graphs, say trees and other graphs resulting from some unary and binary operations, and bounds in terms of other parameters may be determined. Furthermore, since the vertex cover problem is NP -complete, the question as to whether the 2-vertex cover problem is also NP -complete remains unanswered. Acknowledgements The authors would like to thank the referees for reading the initial manuscript and for giving their comments and suggestions. Special thanks must go toMSU-Iligan Institute of Technology, Iligan City, Mindanao State University - Tawi-Tawi College of Technology and Oceanography, Korea University, andWestern Mindanao State University for funding this research. References [1] A. Reis, S. Halper, G. Vezeau, D. Cetnar, A. Hossain, P. Clauer, and H. Salis. Simul- taneous repression of multiple bacterial genes using nonrepetitive extra-long sgrna J. Hassan et. al / Eur. J. Pure Appl. Math, 18 (2) (2025), 6063 11 of 11 arrays. Nature Biotechnology, 37(11):1294–1301, 2019. [2] D. Angel and A. Amutha. Vertex covering and strong covering of flower like network structures. Procedia Computer Science, 87:164–171, 2016. [3] 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. [4] R.M. Karp. Reducibility among combinatorial problems, complexity of computer computations. Plenum Press, New York, pages 85–103, 1972. [5] M.R. Garey and D.S. Johnson. The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 32:826–834, 1977. [6] 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. [7] 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. [8] 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. [9] M. Henning and A. Yeo. Identifying vertex covers in graphs. The Electric Journal in Mathematics,, 19(4):1038–1045., 2012. [10] M. Marathe, R. Ravi, and C. P. Rangan. Generalized vertex covering in interval graphs. Discrete Applied Mathematics, 39:87–93, 1992. [11] P. Pushpam and C. Suseendran. Secure vertex cover of a graph. Discrete Mathematics, Algorithms and Applications, 9(2), 2017. [12] 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. [13] J. Uy. Vertex cover of graphs. Journal of Research in Science and Engineering, 1:49–53, 2003. [14] M. Blidia, M. Chellali, and O. Favaron. Independence and 2-domination in trees. Australas. J. Combin., 33:317–327, 2005. [15] M. Chellali. Bounds on the 2-domination number in cactus graphs. Theoretical Computer Science, 26:5–12, 2006. [16] B. Domoloan and S. Canoy Jr. 2-domination and restrained 2-domination in graphs. Applied Mathematical Sciences, 9(114):5651–5659, 2015. [17] S. Canoy Jr and B. Domoloan. Outer-connected 2-dominating sets of graphs. Ad- vances and Applications in Discrete Mathematics, 20(1):25, 2019. [18] S. Canoy Jr, F. Jamil, R.J. Fortosa, and J. Macalisang. Convex 2-domination in graphs. European Journal of Pure and Applied Mathematics, 17(3):1539–1552, 2024. [19] F. Buckley and F. Harary. Distance in graphs. Addison-Wesley, Redwood City, 1990.