Certified Vertex Cover of a Graph

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