The explorer-director game on graphs

DOI10.1007/S00373-023-02638-8zbMATH Open1515.91036arXiv2104.09451OpenAlexW3152744231MaRDI QIDQ6041379FDOQ6041379

Authors: Pat Devlin, Erin Meger, Abigail Raz 

Publication date: 26 May 2023

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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 on the vertices of a graph. At each time step, the Explorer specifies a distance that the token must move hoping to maximize the amount of vertices ultimately visited, and the Director adversarially chooses where to move token in an effort to minimize this number. Given a graph and a starting vertex, the number of vertices that are visited under optimal play is denoted by $f_d(G,v)$. In this paper, we first reduce the study of $f_d(G,v)$ to the determination of the minimal sets of vertices that are extit{closed} in a certain combinatorial sense, thus providing a structural understanding of each player's optimal strategies. As an application, we address the problem on lattices and trees. 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.

Full work available at URL: https://arxiv.org/abs/2104.09451

Recommendations

• The Magnus-Derek game
• The graph distance game
• More on the Magnus-Derek game
• Palindromes in finite groups and the explorer-director game
• An evasion game on a graph

zbMATH Keywords

games on graphs

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• An \(O(n)\)-round strategy for the Magnus-Derek game
• The Magnus-Derek game
• The Magnus-Derek game in groups
• More on the Magnus-Derek game
• The c game revisited

Cited In (2)

• Palindromes in finite groups and the explorer-director game
• The Magnus-Derek game

This page was built for publication: The explorer-director game on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6041379)