Integer and fractional security in graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Garth Isaak^a ; ^{gisaak@lehigh.edu} ; Peter Johnson^b ; ^{johnspd@auburn.edu} ; Caleb Petrie^b ; ^{cjp0003@auburn.edu}
• 关键词：Secure sets ; Hall&rsquo ; s theorem ; Integer attack ; Integer defense
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：September, 2012
• 卷：160
• 期：13-14
• 页码：2060-2062
• 文件大小：181 K

摘要

Let be a graph. A subset of is said to be secure if it can defend itself from an attack by vertices in . In the usual definition, each vertex in can attack exactly one vertex in , and each vertex in can defend itself or one of its neighbors in . A defense of is successful if each vertex has as many defenders as attackers. We look at allowing an attacking vertex to divide its one unit of attack among multiple targets, or allowing a defending vertex to divide its one unit of defense among multiple allies. Three new definitions of security are given. It turns out that two of the new definitions are the same as the original.