Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.05364 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917328812244992 |
|---|---|
| author | Raz, Abigail Yang, Paddy |
| author_facet | Raz, Abigail Yang, Paddy |
| contents | The Explorer-Director game, first introduced by Nedev and Muthukrishnan (2008), simulates a Mobile Agent exploring a ring network with an inconsistent global sense of direction. Two players, the Explorer and the Director, jointly control a token's movement on the vertices of a graph $G$ with initial location $v$. Each turn, the Explorer calls any valid distance, $d$, aiming to maximize the number of vertices the token visits, and the Director moves the token to any vertex distance $d$ away aiming to minimize the number of visited vertices. The game ends when no new vertices can be visited, assuming optimal play, and we denote the total number of visited vertices by $f_d(G,v)$. Here we study a variant where, if the token is on vertex $u$, the Explorer is allowed to select any valid \emph{path length}, $\ell$, and the Director now moves the token to any vertex $v$ such that $G$ contains a $uv$ path of length $\ell$. The corresponding parameter is $f_p(G,v)$. In this paper, we explore how far apart $f_d(G,v)$ and $f_p(G,v)$ can be, proving that for any $n$ there are graphs $G$ and $H$ with $f_p(G,v)-f_d(G,v)>n$ and $f_d(H,v)-f_p(H,v)>n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05364 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Path Variant of the Explorer Director Game on Graphs Raz, Abigail Yang, Paddy Combinatorics 05C57, 05C12 The Explorer-Director game, first introduced by Nedev and Muthukrishnan (2008), simulates a Mobile Agent exploring a ring network with an inconsistent global sense of direction. Two players, the Explorer and the Director, jointly control a token's movement on the vertices of a graph $G$ with initial location $v$. Each turn, the Explorer calls any valid distance, $d$, aiming to maximize the number of vertices the token visits, and the Director moves the token to any vertex distance $d$ away aiming to minimize the number of visited vertices. The game ends when no new vertices can be visited, assuming optimal play, and we denote the total number of visited vertices by $f_d(G,v)$. Here we study a variant where, if the token is on vertex $u$, the Explorer is allowed to select any valid \emph{path length}, $\ell$, and the Director now moves the token to any vertex $v$ such that $G$ contains a $uv$ path of length $\ell$. The corresponding parameter is $f_p(G,v)$. In this paper, we explore how far apart $f_d(G,v)$ and $f_p(G,v)$ can be, proving that for any $n$ there are graphs $G$ and $H$ with $f_p(G,v)-f_d(G,v)>n$ and $f_d(H,v)-f_p(H,v)>n$. |
| title | A Path Variant of the Explorer Director Game on Graphs |
| topic | Combinatorics 05C57, 05C12 |
| url | https://arxiv.org/abs/2501.05364 |