Let $d(x,y)$ denote the length of a shortest path between vertices $x$ and $y$ in a graph $G$ with vertex set $V$. For a positive integer $k$, let $d_k(x,y)=\min\{ d(x,y), k+1\}$ and $R_k\{ x,y\}=\{ z\in V: d_k(x,z) \neq d_k(y,z)\}$. A set $S \subseteq V$ is a \emph{ distance-$k$ resolving set} of $G$ if $S \cap R_k\{ x,y\} \neq\emptyset$ for distinct $x,y\in V$. In this paper, we study the maker-breaker distance-$k$ resolving game (MB$k$RG) played on a graph $G$ by two players, Maker and Breaker, who alternately select a vertex of $G$ not yet chosen. Maker wins by selecting vertices which form a distance-$k$ resolving set of $G$, whereas Breaker wins by preventing Maker from winning. We denote by $O_{ R,k}(G)$ the outcome of MB$k$RG. Let $\mathcal{ M}$, $\mathcal{ B}$ and $\mathcal{ N}$, respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB$k$RG. Given a graph $G$, the parameter $O_{ R,k}(G)$ is a non-decreasing function of $k$ with codomain $\{ -1=\mathcal{ B}, 0=\mathcal{ N}, 1=\mathcal{ M}\}$. We exhibit pairs $G$ and $k$ such that the ordered pair $(O_{ R,k}(G), O_{ R, k+1}(G))$ realizes each member of the set $\{ (\mathcal{ B}, \mathcal{ N}),(\mathcal{ B}, \mathcal{ M}),(\mathcal{ N},\mathcal{ M})\}$; we provide graphs $G$ such that $O_{ R,1}(G)=\mathcal{ B}$, $O_{ R,2}(G)=\mathcal{ N}$ and $O_{ R,k}(G)=\mathcal{ M}$ for $k\ge3$. Moreover, we obtain some general results on MB$k$RG and study the MB$k$RG played on some graph classes.
Categories: math.CO