The security number of strong grid-like graphs

详细信息    查看全文

• 作者：Ismael Gonz&aacute ; lez Yero^a ; ^{ismael.gonzalez@uca.es" class="auth_mail" title="E-mail the corresponding author} ; Marko Jakovac^b ; ¹ ; ^{marko.jakovac@um.si" class="auth_mail" title="E-mail the corresponding author} ; Dorota Kuziak^c ; ^{dorota.kuziak@urv.cat" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Secure set ; Security number ; Strong product graph ; Grid ; Cylinder ; Torus
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：15 November 2016
• 年：2016
• 卷：653
• 期：Complete
• 页码：1-14
• 全文大小：574 K

文摘

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)$G=(V,E)$ and a set of vertices S⊆V$S\subseteq 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)$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$m,n\ge 4$, s(P_m⊠P_n)=min⁡{m,n,8}$s(P_m⊠P_n)=\min \{m,n,8\}$, s(P_m⊠C_n)=min⁡{2m,n,16}$s(P_m⊠C_n)=\min \{2m,n,16\}$ and s(C_m⊠C_n)=min⁡{2m,2n,32}$s(C_m⊠C_n)=\min \{2m,2n,32\}$.