SECURE POINT SET DOMINATION IN GRAPHS

SECURE POINT SET DOMINATION IN GRAPHS

P. Gupta, A. Goyal

[PDF]

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 2 V D, there exists a vertex v 2 D\N(u) such that (D fvg)[fug 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 su cient for a graph G to satisfy spsd(G) = n - 2.

Keywords

Domination, Point-Set Domination, Secure Domination, Secure Point-Set Domination, Secure Point-Set Domination Number.