Secure point set domination in graphs

Abstract

In this paper, we introduce the notion of secure point-set domination in graphs. A point-set dominating D of graph G is called a secure point-set dominating set if for every vertex u ? V ?D, there exists a vertex v ? D?N(u) such that (D?{v})?{u} is also a point-set dominating set of G. The minimum cardinality of a secure point-set dominating set is called secure point-set domination number of graph G and will be denoted by ?spsd(G) (or simply ?spsd). For any graph G of order n, ?spsd(G) ? 1 and equality holds if and only if G ?= Kn. Also, for any graph G of order n, ?spsd(G) ? n – 1 and equality holds if and only if G ?= K1,n?1. Here we characterize graphs G with ?spsd(G) = 2. We also establish a family F of 11 graphs such that being F-free is necessary as well as sufficient for a graph G to satisfy ?spsd(G) = n ? 2.