The security number of strong grid-like graphs

The concept of a secure set in graphs was first introduced by Brigham et al. in 2007 as a generalization of defensive alliances in graphs. Defensive alliances are related to the defense of a single vertex. However, in a general realistic settings, a defensive alliance should be formed so that any attack on the entire alliance or any subset of the alliance can be defended. In this sense, secure sets represent an attempt to develop a model of this situation. Given a graph G=(V,E) and a set of vertices S⊆V of G, the set S is a secure set if it can defend every attack of vertices outside of S, according to an appropriate definition of “attack” and “defense”. The minimum cardinality of a secure set in G is the security number s(G). In this article we obtain the security number of grid-like graphs, which are the strong products of paths and cycles (grids, cylinders and toruses). Specifically we show that for any two positive integers m,n≥4, s(Pm⊠Pn)=min⁡{m,n,8}, s(Pm⊠Cn)=min⁡{2m,n,16} and s(Cm⊠Cn)=min⁡{2m,2n,32}.