Super Vertex Cover of a Graph

Abstract

A set $S\subseteq V(G)$ is a super vertex cover of $G$ if $S$ is a vertex cover and for every $x\in V(G)\setminus S$, there exists $y\in S$ such that $N_G(y)\cap (V(G)\setminus S)=\{x\}$. The super vertex cover number of $G$, denoted $\beta_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.