2025/01/09 by Raz, Abigail, Yang, Paddy
#05C12 #05C57 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2501.05364
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. The two players, the Explorer and the Director, jointly control the movement of a token on the graph. During each turn, the Explorer calls any valid distance, d, with the aim of maximizing the number of vertices the token visits, and the Director moves the token to any vertex distance d away with the aim of minimizing the number of visited vertices. The game, on graph G with starting vertex v, ends when no new vertices could be visited assuming both players are playing optimally, and we denote the total number of visited vertices by fd(G,v). Since 2008, many authors have explored fd(G,v) for various graph families as well as analyses of complexity. In this work, we study a variation of this game focused on path lengths rather than distances. In this variant, if the token is on vertex u, the Explorer is now allowed to select any valid path length, l, and the Director can now move the token to any vertex v such that G contains a uv path of length l. The corresponding parameter is denoted by fp(G,v). In this paper, we explore how far apart fd(G,v) and fp(G,v) can be for various graph families, proving that for any n there are graphs G and H with fp(G,v)-fd(G,v)>n and fd(G,v)-fp(G,v)>n.