Note: [*] Department of Computer Science and Information Engineering, National Taipei University, New Taipei City 23741, Taiwan.
Note: [**] Department of Applied Mathematics, Chung Yuan Christian University, Taoyuan City 32023, Taiwan.
Abstract: Motivated by the problem of “Defend the Roman Empire”, we propose a variant of graph pebbling, named (d,t)-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 (d,t)-pebbling number of a graph G, denoted by π(d,t)∗(G). When the number of FAs is less than π(d,t)∗(G), 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 π(d,t)∗(G) for d=1,2 and determine the exact value of π(d,t)∗(G) for the ordered pairs (d,t)=(2,2),(1,4m) and (2,10m), where m is any positive integer.
Keywords: Game design, (d, t)-pebbling
DOI: 10.3233/ICG-180052
Journal: ICGA Journal, vol. 40, no. 4, pp. 330-340, 2018
