Secure vertex cover of a graph.

We study the problem of using mobile guards to defend the vertices of a graph against a single attack on its vertices. A vertex cover of a graph is a set such that for each edge , at least one of or is in . The minimum cardinality of a vertex cover is termed the vertex covering number and it is denoted by . In this context, we introduce a new protection strategy called the secure vertex cover SVC problem, where the guards are placed at the vertices of a graph, in order to protect the graph against a single attack on its vertices. We are concerned with the protection of against a single attack, using at most one guard per vertex and require the set of guarded vertices to be a vertex cover. In addition, if any guard moves along an edge to deal with an attack to an unguarded vertex, then the resulting placement of guards must also form a vertex cover. Formally, this protection strategy defends the vertices of a graph against a single attack and simultaneously protects the edges. We define a SVC to be a set such that is a vertex cover and for each , there exists a such that is a vertex cover. The minimum cardinality of an SVC is called the secure vertex covering number and it is denoted by . In this paper, a few properties of SVC of a graph are studied and specific values of for few classes of well-known graphs are evaluated. [ABSTRACT FROM AUTHOR]