EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 1, Article Number 5713 ISSN 1307-5543 – ejpam.com Published by New York Business Global Super Vertex Cover of a Graph Sergio R. Canoy, Jr.1,2, Maria Andrea O. Bonsocan3, Javier A. Hassan4,5,∗, Angelica Mae L. Mahistrado3, Vergel T. Bilar3 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 3 Department of Mathematics, Ateneo de Davao University, E. Jacinto Street, 8016 Davao City, Philippines 4Mathematics and Sciences Department, College of Arts and Sciences, MSU Tawi-Tawi College of Technology and Oceanography, Bongao, Tawi-Tawi, Philippines 5Department of Mathematics, College of Science, Korea University, Seoul 02841, South Korea Abstract. A set S ⊆ V (G) is a super vertex cover of G if S is a vertex cover and for every x ∈ V (G) \ S, there exists y ∈ S such that NG(y) ∩ (V (G) \ S) = {x}. The super vertex cover number of G, denoted βs(G), is the smallest cardinality of a super vertex cover of G. In this paper, we show that the difference of the super vertex cover number and the vertex cover number can be made arbitrarily large. Graphs of small values of the parameter are characterized. Moreover, we give necessary and sufficient conditions for a super vertex cover in the join and the corona of graphs. Corresponding value of the super vertex cover number of each these graphs is also determined. 2020 Mathematics Subject Classifications: 05C69 Key Words and Phrases: Vertex cover, super vertex cover, super vertex cover number 1. Introduction Numerous studies have been made on the vertex covering of a graph (for some studies, see [9], [10], [20], [23]) since the introduction of the concept. As mentioned by Angel and Amutha in [1], the parameter can be used for safety purposes in a network. In particular, the paper pointed out that in a computer network, the minimum value of the parameter offers an optimal solution for designing the network defense strategy. According to Toregas ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i1.5713 Email addresses: sergio.canoy@g.msuiit.edu.ph (S. R. Canoy Jr.), maobonsocan@addu.edu.ph (M. A. Bonsocan), javierhassan@msutawi-tawi.edu.ph (J. A. Hassan), amlmahistrado@addu.edu.ph (A. M. Mahistrado)vtbilar@addu.edu.ph (V. T. Bilar) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 2 of 13 et al. [21], problems involving this concept is also utilized to determine emergency facility location in telecommunication networks. However, the vertex cover problem is an NP- hard optimization problem. In fact, using the known result that the clique problem is NP -complete, Karp [11] proved that the vertex cover problem is also NP -complete. It should be noted that the problem remains NP -complete in cubic graphs and in planar graphs (see [6] and [7]). Studies that dealt with determining bounds and exact values of the vertex cover num- bers of some specific graphs can be found in [2] and [22]. Recently, a number of variations of the vertex cover had been introduced and investigated (see [1], [3], [8], [9], [15], [18], and [19]). Motivated by the introduction of these several variants of the parameter, we introduce and initiate the study of super vertex cover of a graph. As the concept sug- gests, this new parameter combines two existing concepts, namely; vertex cover and super domination. Some studies on super domination can be found in [5], [12],[13], [14], [16], [17]. 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)}, 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. The sets I(G), L(G), and S(G) will, respectively, denote the sets containing all the isolated vertices, leaves, and support vertices in G. 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 super dominating set if for every v ∈ V (G) \S there exists w ∈ S such that NG(w)∩ [V (G) \S] = {v}. The domination number (super domination number) of G, denoted γ(G) (resp. γsp(G)) is the minimum cardinality of a dominating (resp. super dominating) set in G. Any dominating set (super dominating set) with cardinality γ(G) (resp. γsp(G)) is called a γ-set (resp. γsp-set). A subset U of vertices of a graph G is called a vertex cover of G if for every edge e = uv ∈ E(G), u ∈ U or v ∈ U . The minimum cardinality of vertex cover of G is the vertex cover number ofG and is denoted by β(G) and any vertex cover ofG with cardinality β(G) is called a β-set. Clearly, a vertex cover is also a dominating set in a non-trivial connected graph G. A set S ⊆ V (G) is called super vertex cover of G if S is a vertex cover and for every x ∈ V (G)\S, there exists z ∈ S such that NG(z)∩[V (G)\S] = {x}. In other words, a super vertex cover is any set that is both a vertex cover and super dominating set in G. The super vertex cover number of G, denoted by βs(G), is the smallest cardinality S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 3 of 13 of a super vertex cover of G. Any super vertex cover of G with cardinality βs(G) is called a βs-set. 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. Readers are referred to [4] for other basic definitions that are not given here. 3. Results Remark 1. Let G be a graph and let S be a super vertex cover of G. Then each of the following holds: (i) S is a dominating set in G. (ii) I(G) ⊆ S where I(G) is the set containing all the isolated vertices of G. (iii) If v is a support vertex in G, then |(NG[v]∩L(G))∩ (V (G) \S)| ≤ 1, where L(G) is the set of all leaves (end vertices) in G. Proposition 1. Let G be a graph of order n such that E(G) ̸= ∅. Then max{γsp(G), β(G)} ≤ βs(G) ≤ n− 1. Proof. Since every super vertex cover of G is both a vertex cover and a super domi- nating set in G, it follows that max{γsp(G), β(G)} ≤ βs(G). Now let e = uv ∈ E(G) and set S = V (G) \ {u}. Then clearly, S is a super vertex cover of G. Thus, βs(G) ≤ |S| = n− 1. Remark 2. The bounds given in Proposition 1 are sharp. Moreover, strict inequality is attainable. To see this, consider the graphs G1 = P5 = [a, b, c, d, e], G2 = C4 = [x, y, z, w, x], and the star graph G3 = K1, 4. The set T = {b, c, d} is a β-set, γsp-set, and βs-set in G1. Hence, γsp(G1) = β(G1) = βs(G1) = 3 < 4 = |V (G1)| − 1. On the other hand, sets S1 = {x, y}, S2 = {x, z}, and S3 = {x, y, z} are γsp-set, β-set, and βs-set in G2, respectively. Thus, γsp(G2) = β(G2) = 2 < 3 = βs(G2) = |V (G2)| − 1. Finally, one can easily see that β(G3) = 1 < 4 = βs(G3) = γsp(G3) = |V (G3)| − 1. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 4 of 13 For strict inequality, let G be the graph in Figure 1. Set {d, e, c} is a β-set, {a, e, f, g} is a γsp-set, and {a, b, e, f, g} is a βs-set in G. Hence, β(G) = 3 < 4 = γsp(G) < 5 = βs(G) < 6 = |V (G)| − 1. a d b c e f g Figure 1: A graph G with βs(G) = 5 Theorem 1. Let G be a graph of order n such that E(G) ̸= ∅. Then βs(G) = n − 1 if and only if for every pair of non-adjacent vertices v and w of G, and for any x ∈ V (G) with x ∈ NG(v) \NG(w) (x ∈ NG(w) \NG(v)), it holds that NG(w) \NG(x) = ∅ ( resp. NG(v) \NG(x) = ∅). Proof. Suppose βs(G) = n−1. Suppose further that there exist a pair of non-adjacent vertices v and w and a vertex x such that x ∈ NG(v) \ NG(w) but NG(w) \ NG(x) ̸= ∅. Pick any z ∈ NG(w) \NG(x) and let S = V (G) \ {x,w}. Then S is a super vertex cover of G. Hence, βs(G) ≤ |S| = n − 2, a contradiction. Therefore, the condition or property holds. For the converse, suppose that the property holds. Let S0 be a βs-set in G. By Proposition 1, βs = |S0| ≤ n− 1. Suppose |S0| < n− 1. Then there exist p, q ∈ V (G) \S0. Since S0 is a vertex cover of G, pq /∈ E(G). Since S is a super dominating set in G, there exist vp, vq ∈ S such that NG(vp) ∩ [V (G) \ S0] = {p} and NG(vq) ∩ [V (G) \ S0] = {q}. This implies that p ∈ NG(vp) \NG(q). By our assumption that the given property holds, it follows that NG(q) \ NG(p) = ∅. This forces vq ∈ NG(p) because vq ∈ NG(q). This contradicts the property of vertex vq. Thus, βs = |S0| = n− 1. The next result is immediate from Theorem 1. Corollary 1. Let n be a positive integer. Then each of the following holds: (i) βs(Kn) = n− 1 for n ≥ 2. (ii) βs(K1,n−1) = n− 1 for n ≥ 2. It is well known that γsp(G) ≥ n 2 and α(G) + β(G) = n for every graph G of order n. The next remark follows from these facts and Proposition 1. Remark 3. If G is a graph of order n, then βs(G) ≥ max{n 2 , n− α(G)}. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 5 of 13 Proposition 2. Let G1, G2, . . . , Gk be the components of G. Then βs(G) = ∑k j=1 βs(Gj). Proof. Let S be a βs-set in G. For each j ∈ [k] = {1, 2, · · · , k}, let Sj = S ∩ V (Gj). Then S = ∪k j=1Sj . Let j ∈ [k]. Since S is a super vertex cover of G, Sj is a vertex cover of Gj for each j ∈ [k]. Thus, βs(G) = |S| = | ∪k j=1 Sj | = k∑ j=1 |Sj | ≥ k∑ j=1 βs(Gj). For each j ∈ [k], let Dj be a βs-set in Gj . Clearly, D = ∪k j=1Dj is a super vertex cover of G. Hence, βs(G) ≤ |D| = | ∪k j=1 Dj | = k∑ j=1 |Dj | = k∑ j=1 βs(Gj). This proves the assertion. Theorem 2. Let G be any graph on n ≥ 1 vertices. Then each of the following holds: (i) βs(G) = 1 if and only if G ∈ {K1,K2}. (ii) βs(G) = 2 if and only if G ∈ {K2,K3, P3,K1 ∪K2, P4,K2 ∪K2}. (iii) βs(G) = n if and only if G = Kn Proof. (i) Suppose βs(G) = 1. By Remark 3, n ≤ 2. If n = 1, then G = K1. If n = 2, then G = K2. Hence, G ∈ {K1,K2}. The converse is clear. (ii) Suppose βs(G) = 2. By Remark 3 and part (i), 2 ≤ n ≤ 4. If n = 2, then G = K2 by part (i) and Proposition 2. If n = 3 and G is connected, then G ∈ {K3, P3}. If G is disconnected, then G = K1 ∪ K2 by part (i) and Proposition 2. Suppose n = 4. Let S = {a, b} be a βs-set in G and let x, y ∈ V (G) \ S. Since S is a super dominating set in G, we may assume that NG(a) ∩ (V (G) \ S) = {x} and NG(b) ∩ (V (G) \ S) = {y}. Since S is a vertex cover and x, y /∈ S, it follows that xy /∈ E(G). If ab ∈ E(G), then G = P4. If ab /∈ E(G), then G = ⟨{a, x}⟩ ∪ ⟨{b, y}⟩ = K2 ∪ K2. Accordingly, G ∈ {K2,K3, P3,K1 ∪K2, P4,K2 ∪K2}. The converse is clear. (iii) Suppose βs(G) = n. Suppose G ̸= Kn. Then E(G) ̸= ∅. By Proposition 1, we have βs(G) ≤ n− 1, a contradiction. Thus, G = Kn. For the converse, suppose G = Kn. By (i) and Proposition 2, βs(G) = n. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 6 of 13 Proposition 3. Let n be any positive integer. Then βs(Pn) =  1 if n = 1, 2 2 if n = 3, 4 3r if n = 5r 3r + 1, if n = 5r + 1 or n = 5r + 2 3r + 2, if n = 5r + 3 or n = 5r + 4. Proof. Clearly, βs(P1) = βs(P2) = 1 and βs(P3) = βs(P4) = 2. Next, let n = 5r and let P5r = [v1, v2, v3, v4, v5, · · · , v5r−3, v5r−2, v5r−1, v5r]. Then S1 = {v2, v7, · · · , v5r−3} ∪ {v3, v8, · · · , v5r−2} ∪ {v5, v10, · · · , v5r} is a βs-set in P5r. Hence, βs(P5r) = |S1| = 3r. If n = 5r + 1 and if P5r+1 = [v1, v2, v3, v4, v5, · · · , v5r−3, v5r−2, v5r−1, v5r, v5r+1], then S2 = {v2, v7, · · · , v5r−3} ∪ {v3, v8, · · · , v5r−2} ∪ {v5, v10, · · · , v5r} ∪ {v5r+1} is a βs-set in P5r+1. This implies that βs(P5r+1) = |S2| = 3r + 1. If n = 5r + 2 and if P5r+2 = [v1, v2, v3, v4, v5, · · · , v5r−3, v5r−2, v5r−1, v5r, v5r+1, v5r+2], then S3 = {v2, v7, · · · , v5r−3} ∪ {v3, v8, · · · , v5r−2} ∪ {v5, v10, · · · , v5r} ∪ {v5r+2} is a βs-set in P5r+2. It follows that βs(P5r+2) = |S3| = 3r + 1. It is routine to show that βs(P5r+3) = βs(P5r+4) = 3r + 2. Proposition 4. Let n be any positive integer where n ≥ 3. Then βs(Cn) =  2 if n = 3 3 if n = 4 3r if n = 5r 3r + 1, if n = 5r + 1 or n = 5r + 2 3r + 2, if n = 5r + 3 or n = 5r + 4. Proof. It can be verified easily that βs(C3) = 2 and βs(C4) = 3. Let n = 5r and let C5r = [v1, v2, v3, v4, v5, · · · , v5r−3, v5r−2, v5r−1, v5r, v1]. Then D1 = {v1, v6, · · · , v5r−4} ∪ {v2, v7, · · · , v5r−3} ∪ {v4, v9, · · · , v5r−1} is a βs-set in C5r. Hence, βs(C5r) = |D1| = 3r. If n = 5r + 1 and if C5r+1 = [v1, v2, v3, v4, v5, · · · , v5r−3, v5r−2, v5r−1, v5r, v5r+1], then D2 = {v1, v6, · · · , v5r−4} ∪ {v2, v7, · · · , v5r−3} ∪ {v4, v9, · · · , v5r−6, v5r−1} is a βs-set in C5r+1. This implies that βs(C5r+1) = |D2| = 3r + 1. If n = 5r + 2 and if C5r+2 = [v1, v2, v3, v4, v5, · · · , v5r−4, v5r−3, v5r−2, v5r−1, v5r, v5r+1, v5r+2], then D3 = {v1, v6, · · · , v5r−4} ∪ {v2, v7, · · · , v5r−3} ∪ {v4, v9, · · · , v5r−1} ∪ {v5r} is a βs-set in C5r+2. It follows that βs(C5r+2) = |D3| = 3r + 1. That βs(C5r+3) = βs(C5r+4) = 3r + 2 can be shown easily. Theorem 3. Let a and b be positive integers such that 1 ≤ a ≤ b. Then there exists a connected graph G such that β(G) = a and βs(G) = b. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 7 of 13 Proof. If a = b, then considerG = Ka+1. Clearly, β(G) = a. By Theorem 1, βs(G) = a. Next, suppose a < b and let m = b−a. Let G be the graph obtained from Ka+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. Now if m = 1, then clearly, S2 = {v1, v2, · · · , va+1} is a βs-set in G. Thus, βs(G) = a + 1 = b. Suppose m ≥ 2. Note that the set S3 = {v1, v2, · · · , va+1, x2, · · · , xm} is a super vertex cover of G. It follows that β(G) ≤ |S3| = a + 1 + m − 1 = a + m = b. Let S0 be a βs-set in G. If v1 /∈ S0, then S0 = {v2, · · · , va+1, x1, x2, · · · , xm} because S0 is a vertex cover of G. Thus, β(G) = |S| = m+ a = b− a+ a = b. Suppose v1 ∈ S. Since S is a vertex cover, |V (Ka+1) \ S| ≤ 1. If |V (Ka+1) \ S| = 0, then |S ∩ {x1, x2, · · · , xm}| = m− 1 because S is a super dominating set in G. Again, since S is a super dominating set, |S ∩ {x1, x2, · · · , xm}| = m whenever |V (Ka+1) \ S| = 1. In both cases, we have βs(G) = |S0| = b. ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... ............................................................................................................................................ ............................................................................................................... .................................... ................................................................................................................................................... .................................... .................................... ............ ........... ........... ........... ........... ........... ........... ........... ........... ........... .................................... .................................... ..................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........ .................................... .................................... ......................................................................................................................................................................................................................................................................................................................... ..................................................................................................................................................................................................................................................... .................................... .................................... ............................................................................................................................................ ..................................................................................................................................................................................................................................................... .................................... .................................... ..................................................................................................................................................................................................... .................................... ................................................................................................................................................................................ .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .................................... .................................... ........... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... ...... .................................... .................................... ..................... .................... .................... .................... .................... .................... .................... .................... .................... .................... ........ .................................... .................................... ......... ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ ........ . .................................... .................................... .......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... ......... .................................... .................................... .............. ............. ............. ............. ......... .................................... .................................... ...................................................................................................................... .................................... ..................................... . . v1 v2v3 v4 v5 va+1 ... x1 x2 xm Figure 2 Therefore, the assertion holds. The next result is a consequence of Theorem 3. Corollary 2. Let n be a positive integer. Then there exists a connected graph G such that βs(G) − β(G) = n. In other words, the difference βs(G) − β(G) can be made arbitrarily large. Theorem 4. Let G and H be any graphs. A set C ⊆ V (G +H) is a super vertex cover of G+H if and only if C = CG ∪ CH and satisfies one of the following conditions: (i) CG = V (G) and CH is a super vertex cover of H. (ii) CG = V (G) and CH = V (H) \ {q} where q is an isolated vertex in H. (iii) CH = V (H) and CG is a super vertex cover of G. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 8 of 13 (iv) CH = V (H) and CG = V (G) \ {x} where x is an isolated vertex in G. Proof. Suppose C is super vertex cover of G + H. Let CG = C ∩ V (G) and CH = C ∩ V (H). Suppose CG ̸= V (G) and CH ̸= V (H). Pick any v ∈ V (G) \ CG and p ∈ V (H) \ CH . Then e = vp ∈ E(G) and none of v and p is in C. This implies that C is not a vertex cover in G + H, a contradiction. Thus, CG = V (G) or CH = V (H). Suppose CG = V (G) and let ab ∈ E(H). Since C is a vertex cover of G + H, it follows that a ∈ CH or b ∈ CH . This implies that CH is a vertex cover of H. If CH is a super dominating set in H, then (i) holds. So suppose that CH is not a super dominating set in H. Then there exists a vertex q ∈ V (H) \ CH such that for all z ∈ CH , we have NH(z)∩[V (H)\CH ] ̸= {q}. Suppose q is not an isolated vertex in H. Let z0 ∈ CH∩NH(q) (z0 exists because CH is a vertex cover of H). Then NH(z0) ∩ [V (H) \ CH ] ̸= {q}. It follows that there exists t ∈ NH(z0) ∩ [V (H) \ CH ] such that q ̸= t. This implies that NG+H(w) ∩ [V (G+H) \ C] ̸= {q} for all w ∈ C, contrary to the assumption that C is a super dominating set in G + H. Thus, q is an isolated vertex in H. Since C is a super dominating set in G+H, and q /∈ NH [CH ], it follows that CH = V (H) \ {q}. This shows that (ii) holds. Similarly, (iii) or (iv) holds. Conversely, suppose that C = CG ∪ CH . Suppose that (i) holds. Then clearly, C is a super vertex cover of G+H. Suppose (ii) holds. Since V (G) ⊂ C, every edge of the form vw or vq, where v, w ∈ V (G), is incident to a vertex in C. Now let ab ∈ E(H). Since CH = V (H)\{q}, a, b ∈ CH ⊂ C. Hence, C is a vertex cover of G+H. Since V (G+H)\C = {q}, pick any y ∈ CG = V (G). Then yq ∈ E(G +H) and NG+H(y) ∩ [V (G +H) \ C] = {q}. Thus, C is a super dominating set in G + H. Therefore, C is a super vertex cover in G+H. The same conclusion holds for C if (iii) or (iv) holds. Corollary 3. Let G and H be any two graphs of orders m and n, respectively. Then βs(G+H) = m+ n− 1 if and only if one of the following holds: (i) βs(G) = m− 1 and βs(H) = n− 1. (ii) βs(G) = m− 1 and H = Kn (or βs(H) = n− 1 and G = Km). (iii) G = Km and H = Kn. In particular, βs(Km,n) = m+ n− 1 for m,n ≥ 1. Proof. Suppose βs(G + H) = m + n − 1 and let C be a βs-set in G + H. Suppose βs(G) < m−1 or βs(H) < n−1, say βs(G) < m−1. Let SG be a βs-set inG. By Theorem 4, C = SG∪V (H) is a super vertex cover ofG+H. Hence, βs(G+H) ≤ |C| = n+βs(G) < |C|, a contradiction. It follows that βs(G) ≥ m−1 and βs(H) ≥ n−1. Suppose βs(G) = m−1. If βs(H) = n− 1, then (i) holds. Suppose βs(H) = n. Then H = Kn by Theorem 2(iii). Hence, (ii) holds. If βs(G) = m, then (ii) or (iii) holds. For the converse, suppose (i) holds. By Theorem 4, it follows that βs(G + H) = m+ n− 1. Next, suppose (ii) holds, i.e., βs(G) = m− 1 and H = Kn. If C is a βs-set in G+H, then C satisfies (ii) or (iii) or (iv) (in case G has an isolated vertex) of Theorem S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 9 of 13 4. That is, C = V (H) ∪ CG, where CG is βs-set in G, or C = V (G) ∪ [V (Kn) \ {q} for a q ∈ V (Kn) or C = V (H) ∪ [V (G) \ {x} if x is an isolated vertex in G. This implies that βs(G +H) = m + n − 1. Lastly, suppose (iii) holds. Since βs(G) = m and βs(H) = n and C is a βs-set in G +H, C satisfies (ii) or (iv) of Theorem 4. Therefore, βs(G+H) = m+ n− 1. Corollary 4. Let G and H be any two graphs of orders m and n, respectively, such that βs(G+H) ̸= m+ n− 1. Then βs(G+H) = min{m+ βs(H), n+ βs(G)}. Proof. Let D1 and D2 be βs-sets in G and H, respectively. Then C1 = D2 ∪V (G) and C2 = D1 ∪ V (H) are super vertex covers of G+H by Theorem 4. Therefore, βs(G+H) ≤ min{|C1|, |C2|} = min{m+ βs(H), n+ βs(G)}. Next, let C be a βs-set in G + H. Since βs(G + H) ̸= m + n − 1, βs(G) < m − 1 or βs(H) < n− 1 by Corollary 3. This implies that C satisfies (i) or (iii) of Theorem 4, i.e., C = V (G) ∪ CH or C = V (H) ∪ CG, where CG and CH are super vertex covers of G and H, respectively. It follows that βs(G + H) = |C| ≥ min{m + βs(H), n + βs(G)}. This establishes the desired equality. The next result is immediate from Theorem 4 and Corollary 1(i). Corollary 5. Let G be a graph of order m and let n be any positive integer. Then βs(Kn+G) = min{n+βs(G),m+n−1}. In particular, βs(K1+G) = min{1+βs(G),m}. Moreover, each of the following holds: (i) βs(Fn) = βs(K1 + Pn) = 1 + βs(Pn) for n ≥ 2. (ii) βs(Wn) = βs(K1 + Cn) = 1 + βs(Cn) for n ≥ 3. Theorem 5. Let G be a non-trivial connected graph and let H be any graph. Then S ⊆ V (G ◦H) is a super vertex cover in G ◦H if and only if S = A ∪ (∪v∈V (G)Sv) and satisfies the following conditions: (i) A is a vertex cover in G. (ii) For each v ∈ A ∩NG(V (G) \A), it holds that Sv is a super vertex cover in Hv. (iii) For each v ∈ A \ NG(V (G) \ A), it holds that Sv is a super vertex cover in Hv or Sv = V (Hv) \ {qv} for some isolated vertex qv in Hv. (iv) For each v /∈ A, it holds that Sv = V (Hv). Proof. Suppose S is a super vertex cover in G ◦ H. Let A = C ∩ V (G) and let Sv = C∩V (Hv) for each v ∈ V (G). Then S = A∪(∪v∈V (G)Sv). Let ab ∈ E(G) ⊂ E(G◦H). S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 10 of 13 Since S is a vertex cover in G◦H, it follows that a ∈ A or b ∈ A. Hence, A is a vertex cover in G, showing that (i) holds. Let v ∈ A∩NG(V (G) \A) and let pq ∈ E(Hv) ⊂ E(G ◦H). Again, because S is a vertex cover in G ◦H, p ∈ Sv or q ∈ Sv. This implies that Sv is a vertex cover in Hv. Now, let t ∈ V (Hv) \ Sv. Since S is a super dominating set in G ◦H, there exists x ∈ C such that NG◦H(x) ∩ [V (G ◦H) \ C] = {t}. Since v ∈ NG(V (G) \ A, x ̸= v. This implies that x ∈ Sv and NHv(x) ∩ [V (Hv) \ Sv] = {t}. Thus, Sv is a super dominating set in Hv. This shows that (ii) holds. Suppose now that v ∈ A\NG(V (G)\A). Clearly, Sv is a vertex cover in Hv. If Sv is a super dominating set in Hv, then (iii) holds. So suppose Sv is not a super dominating set in Hv. Then there exists qv ∈ V (Hv) \ Sv such that for all z ∈ Sv, we have NH(z) ∩ [V (Hv) \ Sv] ̸= {qv}. Following a previous argument (see proof of Theorem 4), it can be shown that qv is an isolated vertex in Hv and Sv = V (H) \ {qv}. This shows that (iii) holds. Finally, let v /∈ A and let s ∈ V (Hv). Since C is a vertex cover in G ◦H, v /∈ A, and vs ∈ E(G ◦H), we must have s ∈ Sv. As v was arbitrarily chosen, we have Sv = V (Hv), showing that (iv) holds. For the converse, suppose that S has the given form and satisties conditions (i), (ii), (iii), and (iv). Let xy ∈ E(G ◦ H). If x, y ∈ V (G), then x ∈ A or y ∈ A because of (i). Suppose at most one of x and y is in V (G). We may assume that x ∈ V (G). Then y ∈ V (Hx). If x ∈ A, then xy is incident to x ∈ C. If x /∈ A, then Sx = V (Hx) by (iv). It follows that y ∈ Sv. Hence, xy is incident to y ∈ C. Suppose now that x, y ∈ V (Hv) for some v ∈ V (G). If v /∈ A, then Sv = V (Hv). Hence, x, y ∈ Sv ⊂ C. Suppose that v ∈ A∩NG(V (G)\A). By (ii), Sv is a super vertex cover in Hv. This implies that x ∈ Sv or y ∈ Sv. If v ∈ A \ NG(V (G) \ A), then Sv = V (Hv) \ {qv} for some isolated vertex qv in Hv. Since xy ∈ E(G ◦ H), x ̸= qv and y ̸= qv. Hence, x, y ∈ Sv ⊂ C. Therefore, C is a vertex cover in G ◦ H. Next, let p ∈ V (G ◦ H) \ C and let v ∈ V (G) such that p ∈ V (v + Hv). If p = v, then p /∈ A. By (iv), Sv = V (Hv). Pick any q ∈ Sv. Then NG◦H(q)∩ [V (G ◦H) \C] = {p}. Suppose p ∈ V (Hv). Then p ∈ V (Hv) \Sv. This implies that v ∈ A (otherwise Sv = V (Hv) by (iv), a contradiction). If v ∈ A ∩ NG(V (G) \ A), then Sv is a super dominating set in Hv by (ii). Hence, there exists d ∈ Sv ⊂ C such that NG◦H(d)∩ [V (G ◦H) \C] = NHv(d)∩ [V (Hv) \ Sv] = {p}. If v ∈ A \NG(V (G) \A), then Sv = V (Hv) \ {qv} for some isolated vertex qv in Hv. It follows that p = qv. Clearly, NG◦H(v) ∩ [V (G ◦ H) \ C] = {p}. Therefore, C is a super dominating set in G ◦ H. Accordingly, C is a super vertex cover in G ◦H. Corollary 6. Let G and H be non-trivial connected graphs of orders m and n, respectively. Then βs(G ◦H) = (βs(H)− n+ 1)β(G) +mn. Proof. Let A be a β-set in G, Sv a βs-set in Hv for each v ∈ A, and Sw = V (Hv) for each v ∈ V (G) \ A. Then S = A ∪ (∪v∈V (G)Sv) is a super vertex cover of G ◦ H by Theorem 5. It follows that βs(G ◦H) ≤ |S| = |A|+ ∑ v∈A |Sv|+ ∑ v∈V (G)\A |Sv| S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 11 of 13 = β(G) + β(G)βs(H) + n(m− β(G)) = (βs(H)− n+ 1)β(G) +mn. On the other hand, let C0 be a βs-set in G ◦ H. Then C0 = A0 ∪ (∪v∈V (G)S ′ v) and satisfies properties (i), (ii), (iii), and (iv) of Theorem 5. Hence, A0 is a vertex cover of G by (i) and S′ v = V (Hv) for each v ∈ V (G) \A by (iv). Note that since H is a (non-trivial) connected graph, S′ v is a super vertex cover in Hv for each v ∈ V (G) by (ii) and (iii). Hence, βs(G ◦H) = |S0| = |A0|+ ∑ v∈A0 |S′ v|+ ∑ v∈V (G)\A0 |S′ v| ≥ |A0|+ ∑ v∈A0 βs(H) + ∑ v∈V (G)\A0 n = |A0|+ |A0|βs(H) + (m− |A0|)n = (βs(H)− n+ 1)|A0|+mn ≥ (βs(H)− n+ 1)β(G) +mn. This establishes the desired equality. 4. Conclusion The variant super vertex cover of the standard vertex cover had been introduced and initially investigated in this study. For a non-empty graphG, its super vertex cover number is at least equal to the maximum of the super domination number and the vertex cover number of the graph and at most equal to |V (G)| − 1. It was shown that the difference of the super vertex cover number and the vertex cover number can be made arbitrarily large. In this study, the super vertex cover numbers of some graphs, including the join and the corona of two graphs, had been obtained. Further study or investigation of the newly defined parameter is recommended. In particular, it may be interesting to determine the value of the parameter for graphs resulting from other binary operations. Moreover, while the vertex cover problem is NP -complete, it remains open to show whether or not the super vertex cover problem is NP -complete. Acknowledgements The authors would like to thank the referees for reading the paper and giving their respective comments and suggestions. The authors are grateful to MSU-Iligan Institute of Technology, Iligan City, Ateneo de Davao University, MSU Tawi-Tawi College of Technol- ogy and Oceanography, and Korea University for the financial support they have extended for the conduct of this research. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 12 of 13 References [1] D. Angel and A. Amutha. Vertex covering and strong covering of flower like network structures. Procedia Computer Science, 87:164–171, 2016. [2] 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. [3] 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. [4] F. Buckley and F. Harary. Distance in graphs. Addison-Wesley, Redwood City, 1990. [5] C. Bujtas, N. Ghanbari, and S. Klavzar. Computational complexity aspects of super domination. Theoretical Computer Science, 975:1–13, 2023. [6] M.R. Garey and D.S. Johnson. The rectilinear steiner tree problem is np-complete. SIAM Journal on Applied Mathematics, 32:826–834, 1977. [7] 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. [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] S. Canoy Jr and R. Artes Jr. Vertex and edge covering numbers of a graph: Revisited. Congressus Numerantium, 167:65, 2004. [11] R.M. Karp. Reducibility among combinatorial problems, complexity of computer computations. Plenum Press, New York, pages 85–103, 1972. [12] D. Klein, J. Velazquez, and E. Yi. On the super domination number of graphs. Communications in Combinatorics and Optimization, 5(2):83–96, 2020. [13] M. Lemanska, V. Swaminathan, and Y. B. Venkatakrishnan. Computational com- plexity aspects of super domination. Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 85:353–357, 2015. [14] R. Liguarda and S. Canoy Jr. Connected super domination in graphs. Advances and Applications in Discrete Mathematics, 19(3):273–288, 2018. [15] M. Marathe, R. Ravi, and C. P. Rangan. Generalized vertex covering in interval graphs. Discrete Applied Mathematics, 39:87–93, 1992. [16] S. Paraico and S. Canoy Jr. Super dominating sets in some products of graphs. Far East Journal of Mathematical Sciences, 23(2):187–199, 2015. [17] S. Paraico and S. Canoy Jr. Super domination in graphs. Journal of Analysis & Applications, 15(2):149, 2017. [18] P. Pushpam and C. Suseendran. Secure vertex cover of a graph. Discrete Mathematics, Algorithms and Applications, 9(2), 2017. [19] 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. [20] S. Sitthiwirattham. Vertex covering and independent number on difference graphs. S. R. Canoy et al. / Eur. J. Pure Appl. Math, 18 (1) (2025), 5713 13 of 13 International Journal of Pure and Applied Mathematics, 77(4):543–547, 2012. [21] 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. [22] J. Uy. Vertex cover of graphs. Journal of Research in Science and Engineering, 1:49–53, 2003. [23] J. Uy and V. Abregana. Revisiting the vertex cover of graphs. Applied Mathematical Sciences, 9:5707 – 5714, 2015.