The security number of lexicographic products

Abstract

A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] − S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results.