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.

Mathematics Subject Classification (2010): 05C69, 05C76.

Keywords: Secure set, security number, lexicographic product of graphs