Security in graphs (Q2381534)

For vertices \(v\) in a graph \(G=(V,E)\), let \(N[v]=\{w\in V: wv\in E\}\cup\{v\}\). Given \(S=\{s_1, \dots, s_k\}\subseteq V\), an attack \(A\) on \(S\) is any \(k\) mutually disjoint sets \(A_1,\dots, A_k\) for which \(A_i\subseteq N[s_i]\setminus S\). A defense \(D\) of \(S\) is any \(k\) mutually disjoint sets \(D_1,\dots, D_k\) for which \(D_i\subseteq N[s_i]\cap S\). Attack \(A\) is defendable if there exists a defense \(D\) such that \(| D_i| \geq | A_i| \). Set \(S\) is secure if every attack on \(S\) is defendable. A subet \(X\) of \(S\) is \(S\)-secure if every attack on \(S\) in which \(A_i=\emptyset\) whenever \(s_i\not\in X\) is defendable. Set \(N[S]=\bigcup_{s\in S} N[s]\) and let \(\kappa(\langle S\rangle)\) denote the connectivity number of the subgraph of \(G\) induced by \(S\). Among others, the authors show that the following conditions are equivalent: (1) \(S\) is defendable, (2) \(| S| \geq | N[S]\setminus S| \) and every \(X\subseteq S\) is \(S\)-secure whenever \(| X| \leq | N[X]\setminus S| -1-\kappa(\langle S\rangle)\), (3) For all \(X\subseteq S\), \(| N[X]\cap S| \geq | N[X]\setminus S| \), and (4) \(| S| \geq | N[S]\setminus S| \) and \(S\setminus\{s\}\) is \(S\)-secure for every \(s\in S\). The authors also point out that determining if a fixed attack is defendable is polynomially solvable by giving an equivalent linear program, and propose many open questions for further research.