Geodesic
Introduction to the ``prisoners and guards'' game
Journal of integer sequences, Tome 12 (2009) no. 1
We study the half-dependent problem for the king graph $K_{n}$. We give proofs to establish the values $h(K_{n})$ for $n \in {1,2,3,4,5,6}$ and an upper bound for $h(K_{n})$ in general. These proofs are independent of computer assisted results. Also, we introduce a two-player game whose winning strategy is tightly related with the values $h(K_{n})$. This strategy is analyzed here for $n = 3$ and some facts are given for the case $n = 4$. Although the rules of the game are very simple, the winning strategy is highly complex even for $n = 4$.
Classification : 05D99, 91A05, 91A24
Keywords: upper bounds, winning strategies, maximal configurations, domination in graphs 
@article{JIS_2009__12_1_a2,
     author = {Howard,  Timothy and Ionascu,  Eugen J. and Woolbright,  David},
     title = {Introduction to the ``prisoners and guards'' game},
     journal = {Journal of integer sequences},
     year = {2009},
     volume = {12},
     number = {1},
     zbl = {1167.91005},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2009__12_1_a2/}
}
TY  - JOUR
AU  - Howard,  Timothy
AU  - Ionascu,  Eugen J.
AU  - Woolbright,  David
TI  - Introduction to the ``prisoners and guards'' game
JO  - Journal of integer sequences
PY  - 2009
VL  - 12
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/JIS_2009__12_1_a2/
LA  - en
ID  - JIS_2009__12_1_a2
ER  - 
%0 Journal Article
%A Howard,  Timothy
%A Ionascu,  Eugen J.
%A Woolbright,  David
%T Introduction to the ``prisoners and guards'' game
%J Journal of integer sequences
%D 2009
%V 12
%N 1
%U http://geodesic.mathdoc.fr/item/JIS_2009__12_1_a2/
%G en
%F JIS_2009__12_1_a2
Howard,  Timothy; Ionascu,  Eugen J.; Woolbright,  David. Introduction to the ``prisoners and guards'' game. Journal of integer sequences, Tome 12 (2009) no. 1. http://geodesic.mathdoc.fr/item/JIS_2009__12_1_a2/