Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952446 | Theoretical Computer Science | 2016 | 14 Pages |
Abstract
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}.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ismael González Yero, Marko Jakovac, Dorota Kuziak,