Document Type

Article

Publication Date

2023

Published In

Graphs And Combinatorics

Abstract

The Explorer-Director game, first introduced by Nedev and Muthukrishnan, can be described as a game where two players—Explorer and Director—determine the movement of a token that is positioned on the vertices of some given graph. At each time step, the Explorer specifies a distance that the token must move with an aim to maximize the total number of vertices ultimately visited. However, the Director adversarially chooses where to move token in an effort to minimize this number. The game ends when no new vertices can be visited. Given a graph G and a starting vertex v, the number of vertices that are visited under optimal play is denoted by fd(G,v). In this paper, we first reduce the study of fd(G,v) to the determination of the minimum sets of vertices that are closed in a certain combinatorial sense, thus providing a structural understanding of each player’s optimal strategies. As an application, we provide some exact results as well as more general bounds when G is a square lattice or tree. In the case of trees, we also provide a complete solution even in the more restrictive setting where the strategy used by the Explorer is not allowed to depend on their opponent’s responses. In addition to this paper, a supplementary companion note will be posted to arXiv providing additional results about the game in a variety of specific graph families.

Keywords

Games on graphs

Comments

This work is a preprint that is freely available courtesy of Springer. The version of record can be freely accessed via SpringerNature's SharedIt service.

Download

Available for download on Wednesday, May 01, 2024

Share

COinS