An investigation of the game of Defend the Island

Abstract

Motivated by the problem of “Defend the Roman Empire”, we propose a variant of graph pebbling, named $\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}$ -pebbling, and use this idea to devise a two-player game of imperfect information, named “Defend the Island”. On an island, the target castle attacked by the opponent is securable if t Field Armies (FAs) can reach the target castle from neighboring castles within a distance of d. The aim is to obtain more points than the opponent before an insecure castle on the island is attacked. There is a minimum number of FAs initially deployed on the island so that each castle is securable. In graph pebbling, this number is called the optimal $\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}$ -pebbling number of a graph G, denoted by ${\mathit{\pi }}_{\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}}^{\ast }\mathrm{(}\mathit{G}\mathrm{)}$ . When the number of FAs is less than ${\mathit{\pi }}_{\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}}^{\ast }\mathrm{(}\mathit{G}\mathrm{)}$ , there exists at least one insecure castle. This property is the core idea to devise the new game. In addition, when the castles forms a cycle, that is, the graph is a cycle, we give a lower bound of ${\mathit{\pi }}_{\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}}^{\ast }\mathrm{(}\mathit{G}\mathrm{)}$ for $\mathit{d}=1\mathrm{,}2$ and determine the exact value of ${\mathit{\pi }}_{\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}}^{\ast }\mathrm{(}\mathit{G}\mathrm{)}$ for the ordered pairs $\mathrm{(}\mathit{d}\mathrm{,}\mathit{t}\mathrm{)}=\mathrm{(}2\mathrm{,}2\mathrm{)}\mathrm{,}\mathrm{(}1\mathrm{,}4\mathit{m}\mathrm{)}$ and $\mathrm{(}2\mathrm{,}10\mathit{m}\mathrm{)}$ , where m is any positive integer.