# Maker-Breaker Metric Resolving Games on Graphs

Cong X. Kang1 and Eunjeong Yi2
Texas A&M University at Galveston, Galveston, TX 77553, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

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 _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\geq 3$. Moreover,
we obtain some general results on MB$k$RG and study the MB$k$RG played on some
graph classes.

Keywords: distance-$k$ metric, $k$-truncated metric, resolving set,
$k$-truncated resolving set, distance-$k$ resolving set, Maker-Breaker
distance-$k$ resolving game, Maker-Breaker resolving game

2010 Mathematics Subject Classification: 05C12, 05C57

##  1 Introduction

Games played on graphs have been studied extensively; examples of two-player
games include cop and robber game [21], Hex board game [11], Maker-Breaker
domination game [5], etc. Erdös and Selfridge [6] introduced the Maker-Breaker
game played on an arbitrary hypergraph $H=(V,E)$ by two players, Maker and
Breaker, who alternately select a vertex from $V$ not yet chosen in the course
of the game. Maker wins the game if he can select all vertices of a hyperedge
from $E$, whereas Breaker wins if she is able to prevent Maker from doing so.
For further reading on these games, see [2, 15]. The Maker-Breaker resolving
game (MBRG) was introduced in [18], and its fractionalization was studied in
[26]. As it turns out, on any graph $G$ that is connected, MBRG fits as the
terminal member of a natural family of metric resolving games numbering
$(\textnormal{diam}(G)-1)$ in strength, where $\textnormal{diam}(G)$ is the
length of a longest path found in $G$. In this paper, we introduce and study
this family, and we call a general member of this family the _Maker-Breaker
distance- $k$ resolving game_ (MB$k$RG). As will be made clear shortly,
MB$k$RG equals MBRG when $k=\textnormal{diam}(G)-1$. But first, we need to set
down some basic terminology and notations.

Let $G$ be a finite, simple, undirected, and connected graph with vertex set
$V(G)$ and edge set $E(G)$. Let $k$ be a member of the set $\mathbb{Z}^{+}$ of
positive integers. For $x,y\in V(G)$, let $d(x,y)$ denote the minimum number
of edges in a path linking $x$ and $y$ in $G$, and let
$d_{k}(x,y)=\min\\{d(x,y),k+1\\}$. Thus, $d(\cdot,\cdot)$ is the usual,
shortest-path metric on $G$, and we can call $d_{k}(\cdot,\cdot)$ the
_distance- $k$_ or the _$k$ -truncated metric_ on $G$. For distinct $x,y\in
V(G)$, let $R\\{x,y\\}=\\{z\in V(G):d(x,z)\neq d(y,z)\\}$ and
$R_{k}\\{x,y\\}=\\{z\in V(G):d_{k}(x,z)\neq d_{k}(y,z)\\}$. A set $S\subseteq
V(G)$ is a _resolving set_ of $G$ if $S\cap R\\{x,y\\}\neq\emptyset$ for
distinct $x,y\in V(G)$, and the _metric dimension_ $\dim(G)$ of $G$ is the
minimum cardinality over all resolving sets of $G$. Similarly, a set
$S\subseteq V(G)$ is a _distance- $k$ resolving set_ (also called a _$k$
-truncated resolving set_) of $G$ if $S\cap R_{k}\\{x,y\\}\neq\emptyset$ for
distinct $x,y\in V(G)$, and the _distance- $k$ metric dimension_ (also called
the _$k$ -truncated metric dimension_) $\dim_{k}(G)$ of $G$ is the minimum
cardinality over all distance-$k$ resolving sets of $G$. For an ordered set
$S=\\{u_{1},u_{2},\ldots,u_{\alpha}\\}\subseteq V(G)$ and for a vertex $v\in
V(G)$, the metric code of $v$ with respect to $S$ is the $\alpha$-vector
$\textnormal{code}_{S}(v)=(d(v,u_{1}),d(v,u_{2}),\ldots,d(v,u_{\alpha}))$. We
note that $S$ is a resolving set of $G$ if and only if the map
$\textnormal{code}_{S}(\cdot)$ is injective on $V(G)$. By replacing the metric
$d(\cdot,\cdot)$ by $d_{k}(\cdot,\cdot)$ mutatis mutandis, the notion of a
distance-$k$ metric code map $\textnormal{code}_{S,k}(\cdot)$ on $V(G)$ and a
distance-$k$ resolving set are analogously defined; note that, again,
$S\subseteq V(G)$ is a distance-$k$ resolving set of $G$ if and only if the
map $\textnormal{code}_{S,k}(\cdot)$ is injective on $V(G)$.

The concept of metric dimension was introduced in [14, 23], and the concept of
distance-$k$ metric dimension was introduced in [1, 7]. For further study on
distance-$k$ metric dimension of graphs, see [10], which is a result of
merging [13] and [25] with some additional results, and [25] is based on [24].
Some applications of metric dimension include robot navigation [19], network
discovery and verification [3], chemistry [20], sonar [23] and combinatorial
optimization [22]. For applications of distance-$k$ metric dimension see [10,
17], where sensors/landmarks are placed at locations (vertices) forming a
distance-$k$ resolving set of a network, with the understanding that the cost
of a sensor/landmark increases as its detection range increases. It is known
that determining the metric dimension of a general graph is an NP-hard problem
([12, 19]) and that determining the distance-$k$ metric dimension of a general
graph is an NP-hard problem ([8, 9]).

Returning to the eponymous games of this paper, and following [18], MBRG
(MB$k$RG, respectively) is played on a graph $G$ by two players, Maker (also
called Resolver) and Breaker (also called Spoiler), denoted by $M^{*}$ and
$B^{*}$, respectively. $M^{*}$ and $B^{*}$ alternately select (without missing
their turn) a vertex of $G$ that was not yet chosen in the course of the game.
$M$-game ($B$-game, respectively) denotes the game for which $M^{*}$ ($B^{*}$,
respectively) plays first. $M^{*}$ wins the MBRG (MB$k$RG, respectively) if he
is able to select vertices that form a resolving set (a distance-$k$ resolving
set, respectively) of $G$ in the course of the game, and $B^{*}$ wins MBRG
(MB$k$RG, respectively) if she stops Maker from winning. We denote by
$O_{R}(G)$ and $O_{R,k}(G)$ the outcomes, respectively, of MBRG and MB$k$RG
played on a graph $G$. Noting that there’s no advantage for the second player
in the MBRG, it was observed in [18] that there are three realizable outcomes,
as follows: $O_{R}(G)=\mathcal{M}$ if $M^{*}$ has a winning strategy whether
he plays first or second in the MBRG, $O_{R}(G)=\mathcal{B}$ if $B^{*}$ has a
winning strategy whether she plays first or second in the MBRG, and
$O_{R}(G)=\mathcal{N}$ if the first player has a winning strategy in the MBRG.
Analogously, we assign to $O_{R,k}(G)$ an element of
$\\{\mathcal{M},\mathcal{B},\mathcal{N}\\}$ in accordance with each of the
aforementioned outcomes.

The authors of [18] studied the minimum number of moves needed for $M^{*}$
($B^{*}$, respectively) to win the MBRG provided $M^{*}$ ($B^{*}$,
respectively) has a winning strategy. In MBRG, let $M_{R}(G)$
($M^{\prime}_{R}(G)$, respectively) denote the minimum number of moves for
$M^{*}$ to win the $M$-game ($B$-game, respectively) provided he has a winning
strategy with $O_{R}(G)=\mathcal{M}$, and let $B_{R}(G)$ ($B^{\prime}_{R}(G)$,
respectively) denote the minimum number of moves for $B^{*}$ to win the
$M$-game ($B$-game, respectively) provided she has a winning strategy with
$O_{R}(G)=\mathcal{B}$. Suppose rivals $X$ and $Y$ compete to gain control
over a network $Z$, with $X$ trying to install transmitters with limited range
at certain nodes to form a distance-$k$ resolving set of the network, while
$Y$ seeks to sabotage the effort by $X$. In this scenario, time becomes a
matter of natural concern. If $O_{R,k}(G)=\mathcal{M}$, then we denote by
$M_{R,k}(G)$ ($M^{\prime}_{R,k}(G)$, respectively) the minimum number of moves
for $M^{*}$ to win the $M$-game ($B$-game, respectively). If
$O_{R,k}(G)=\mathcal{B}$, then we denote by $B_{R,k}(G)$
($B^{\prime}_{R,k}(G)$, respectively) the minimum number of moves for $B^{*}$
to win the $M$-game ($B$-game, respectively). If $O_{R,k}(G)=\mathcal{N}$,
then we denote by $N_{R,k}(G)$ ($N^{\prime}_{R,k}(G)$, respectively) the
minimum number of moves for the first player to win the $M$-game ($B$-game,
respectively).

Now, we recall a bit more terminology and notations. The _diameter_ ,
$\textnormal{diam}(G)$, of $G$ is $\max\\{d(x,y):x,y\in V(G)\\}$. For $v\in
V(G)$, the _open neighborhood_ of $v$ is $N(v)=\\{u\in V(G):uv\in E(G)\\}$,
and the _degree_ of $v$ is $|N(v)|$; a _leaf_ (or an _end-vertex_) is a vertex
of degree one, and a _major vertex_ is a vertex of degree at least three. Let
$P_{n}$, $C_{n}$ and $K_{n}$ respectively denote the path, the cycle and the
complete graph on $n$ vertices. For positive integers $s$ and $t$, let
$K_{s,t}$ denote the complete bi-partite graph with two parts of sizes $s$ and
$t$. For $\alpha\in\mathbb{Z}^{+}$, let $[\alpha]$ denote the set
$\\{1,2,\ldots,\alpha\\}$.

This paper is organized as follows. In Section 2, we study the parameter
$O_{R,k}(G)$ as a function of $k$. We exhibit pairs $G$ and $k$ such that the
ordered pair $(O_{R,k-1}(G),O_{R,k}(G))$ realizes each member of the set
$\\{(\mathcal{B},\mathcal{N}),(\mathcal{B},\mathcal{M}),(\mathcal{N},\mathcal{M})\\}$,
and we define an MB$k$RG-outcome-transition number (a jump) as an integer
$k>1$ such that $O_{R,k-1}(G)\neq O_{R,k}(G)$. In Section 3, we examine
$O_{R,k}(G)$ when $G$ is the Petersen graph, a complete multipartite graph, a
wheel graph, a cycle, and a tree with some restrictions.

##  2 The parameter $O_{R,k}(G)$ as a function of $k$

To facilitate our discussion of $O_{R,k}(G)$ as a function of $k$, let us
assign outcomes $\mathcal{B},\mathcal{N},\text{and\ }\mathcal{M}$ the values
of $-1,0,\text{and\ }1$, respectively, and hence we have
$\mathcal{B}<\mathcal{N}<\mathcal{M}$. It is clear from the definitions that
$d_{k+1}(x,y)\geq d_{k}(x,y)$ and, for $k\geq\textnormal{diam}(G)-1$,
$d_{k}(x,y)=d(x,y)$. Thus, we can identify $d(x,y)$ with $d_{k}(x,y)$ for any
$k\geq\textnormal{diam}(G)-1$; we can likewise identify $O_{R}(G)$ with
$O_{R,k}(G)$ for any $k\geq\textnormal{diam}(G)-1$. The following observation
is instrumental to studying MB$k$RG as a function of $k$.

######  Observation 2.1.

On any graph, a distance-$k$ resolving set is a distance-$(k+1)$ resolving
set.

The preceding observation easily leads to the following two observations,
which are found in existing literature.

######  Observation 2.2.

_[1]_ Let $G$ be a connected graph, and let $k,k^{\prime}\in\mathbb{Z}^{+}$
with $k<k^{\prime}$. Then $\dim_{k}(G)\geq\dim_{k^{\prime}}(G)\geq\dim(G)$.

######  Observation 2.3.

_[7]_ Let $k\in\mathbb{Z}^{+}$ and $G$ be a connected graph.

  * (a)

If $\textnormal{diam}(G)\in\\{1,2\\}$, then $\dim_{k}(G)=\dim(G)$ for all $k$.

  * (b)

More generally, $\dim_{k}(G)=\dim(G)$ for all $k\geq\textnormal{diam}(G)-1$.

The following monotonicity result follows readily from the rules of MB$k$RG
and Observation 2.1.

######  Proposition 2.4.

On any graph $G$, the parameter $O_{R,k}(G)$ is a non-decreasing function of
$k$, where the codomain is $\\{\mathcal{B}=-1,\mathcal{N}=0,\mathcal{M}=1\\}$.

It’s worth noting that there are exactly ${\textnormal{diam}(G)+1\choose 2}$
monotone functions from $[\textnormal{diam}(G)-1]$ to $\\{-1,0,1\\}$. To see
this, observe that such a function is but a vector consisting of a string of
$-1$’s, followed by a string of $0$’s, and then followed by a string of $1$’s,
satisfying $a+b+c=\textnormal{diam}(G)-1$ and
$a,b,c\in\\{0\\}\cup\mathbb{Z}^{+}$, where $a$, $b$, and $c$ respectively
denote the number of $-1$’s, $0$’s, and $1$’s. The number of solutions to the
diophantine equation clearly equals the number of monomials of total degree
$(\textnormal{diam}(G)-1)$ in $3$ symbols, and the latter is well known to be
the combinatoric symbol asserted. Now, we spotlight a few key results among
the bounty of consequences yielded by Proposition 2.4.

######  Corollary 2.5.

Let $k\in\mathbb{Z}^{+}$ and $G$ be a connected graph.

  * (a)

If $\textnormal{diam}(G)\in\\{1,2\\}$, then $O_{R,k}(G)=O_{R}(G)$ for all $k$.

  * (b)

Given $k<k^{\prime}$, we have
$(O_{R,k}(G),O_{R,k^{\prime}}(G))\in\\{(\mathcal{B},\mathcal{B}),(\mathcal{N},\mathcal{N}),(\mathcal{M},\mathcal{M})$,
$(\mathcal{B},\mathcal{N}),(\mathcal{B},\mathcal{M}),(\mathcal{N},\mathcal{M})\\}$;
note that $O_{R,k_{0}}(G)$ is $O_{R}(G)$ for
$k_{0}\geq\textnormal{diam}(G)-1$.

The monotonicity of $O_{R,k}(G)$ as a function of $k$ with codomain
$\\{\mathcal{B},\mathcal{N},\mathcal{M}\\}$ prompts natural questions. Given a
graph $G$, what is the range of $O_{R,k}(G)$? Also, where does the function
“jump value”? To this end, for
$X,Y\in\\{\mathcal{B},\mathcal{N},\mathcal{M}\\}$ with $X<Y$, define _the MB
$k$RG-outcome-transition number (the jump) of $G$ from $X$ to $Y$_, denoted by
$O^{T}_{X,Y}(G)$, to be the number $\alpha\in[\textnormal{diam}(G)-1]-\\{1\\}$
satisfying $O_{R,\alpha-1}(G)=X$ and $O_{R,\alpha}(G)=Y$, when such an
$\alpha$ exists; put $O^{T}_{X,Y}(G)=\emptyset$ otherwise. Clearly, each graph
$G$ has no more than two jumps and, if
$O^{T}_{\mathcal{B},\mathcal{M}}(G)\neq\emptyset$, then $G$ has only one jump.

Now, we work towards realization results in conjunction with Proposition 2.4
and Corollary 2.5. First, we recall some terminology. Two vertices $u$ and $w$
are called _twins_ if $N(u)-\\{w\\}=N(w)-\\{u\\}$; notice that a vertex is its
own twin. Hernando et al. [16] observed that the twin relation is an
equivalence relation on $V(G)$ and, under it, each (_twin_) equivalence class
induces either a clique or an independent set. The next few results involve
twin equivalence classes.

######  Observation 2.6.

Let $x$ and $y$ be distinct members of the same twin equivalence class of $G$.

  * (a)

_[16]_ If $R$ is a resolving set of $G$, then $R\cap\\{x,y\\}\neq\emptyset$.

  * (b)

_[10]_ If $R_{k}$ is a distance-$k$ resolving set of $G$, then
$R_{k}\cap\\{x,y\\}\neq\emptyset$.

######  Proposition 2.7.

Let $G$ be a connected graph of order at least $4$.

  * (a)

_[18]_ If $G$ has a twin equivalence class of cardinality at least $4$, then
$O_{R}(G)=\mathcal{B}$.

  * (b)

_[18]_ If $G$ has two distinct twin equivalence classes of cardinality at
least $3$, then $O_{R}(G)=\mathcal{B}$.

  * (c)

_[26]_ If $G$ has $k\geq 0$ twin equivalence class(es) of cardinality $2$ and
exactly one twin equivalence class of cardinality $3$ with $\dim(G)=k+2$, then
$O_{R}(G)=\mathcal{N}$.

######  Corollary 2.8.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a connected graph of order at least
$4$.

  * (a)

If $G$ has a twin equivalence class of cardinality at least $4$, then
$O_{R,k}(G)=\mathcal{B}$ for all $k$.

  * (b)

If $G$ has two distinct twin equivalence classes of cardinality $3$, then
$O_{R,k}(G)=\mathcal{B}$ for all $k$.

Here is a relation between $\dim_{k}(G)$ and $O_{R,k}(G)$, which is analogous
to the relation between $\dim(G)$ and $O_{R}(G)$ obtained in [18].

######  Observation 2.9.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a connected graph of order $n\geq 2$.

  * (a)

If $O_{R,k}(G)=\mathcal{M}$, then $\dim_{k}(G)\leq\lfloor\frac{n}{2}\rfloor$.

  * (b)

If $\dim_{k}(G)\geq\lceil\frac{n}{2}\rceil+1$, then $O_{R,k}(G)=\mathcal{B}$.

###### Proof.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a connected graph of order $n\geq 2$.

(a) Let $O_{R,k}(G)=\mathcal{M}$. Assume, to the contrary, that
$\dim_{k}(G)>\lfloor\frac{n}{2}\rfloor$. In the $B$-game of the MB$k$RG,
$M^{*}$ can occupy at most $\lfloor\frac{n}{2}\rfloor$ vertices, and hence
$M^{*}$ fails to occupy a distance-$k$ resolving set of $G$; thus,
$O_{R,k}(G)\neq\mathcal{M}$, which contradicts the hypothesis.

(b) Let $\dim_{k}(G)\geq\lceil\frac{n}{2}\rceil+1$. In the $M$-game of the
MB$k$RG, $M^{*}$ can occupy at most $\lceil\frac{n}{2}\rceil$ vertices of $G$;
thus, $M^{*}$ fails to occupy vertices that form a distance-$k$ resolving set
of $G$. Since $B^{*}$ has a winning strategy for the $M$-game in the MB$k$RG,
$O_{R,k}(G)=\mathcal{B}$. ∎

Analogous to the concept of a pairing dominating set (see [5]) and a pairing
resolving set (see [18]), we define a pairing distance-$k$ resolving set and a
quasi-pairing distance-$k$ resolving set of a graph.

######  Definition 2.10.

Let $k,\alpha\in\mathbb{Z}^{+}$ and $G$ be a connected graph. Let
$X=\displaystyle\bigcup_{i\in[\alpha]}\\{\\{u_{i},w_{i}\\}\\}$, where $\bigcup
X\subseteq V(G)$ and $|\bigcup X|=2\alpha$. Let $Z\subseteq V(G)$ be such that
$|Z|=\alpha$ and $Z\cap\\{u_{i},w_{i}\\}\neq\emptyset$ for each
$i\in[\alpha]$.

  * (a)

Suppose each $Z$, as defined, is a distance-$k$ resolving set of $G$, then $X$
is called a _pairing distance- $k$ resolving set_ of $G$.

  * (b)

Suppose each $Z$, as defined, fails to be a distance-$k$ resolving set of $G$,
and there exists a vertex $v\in V(G)-\bigcup X$ such that $Z\cup\\{v\\}$ is a
distance-$k$ resolving set of $G$ for each $Z$, then $X$ is called a _quasi-
pairing distance- $k$ resolving set_ of $G$.

######  Observation 2.11.

_[18]_ If $G$ admits a pairing resolving set, then $O_{R}(G)=\mathcal{M}$.

######  Observation 2.12.

Let $k\in\mathbb{Z}^{+}$, and let $G$ be a connected graph of order at least
two.

  * (a)

If $G$ admits a pairing distance-$k$ resolving set, then
$O_{R,k}(G)=\mathcal{M}$.

  * (b)

If $G$ admits a quasi–pairing distance-$k$ resolving set, then
$O_{R,k}(G)\in\\{\mathcal{M},\mathcal{N}\\}$.

Now, we present the main theorem of this section, which is a collection of
realization results (to wit, examples) which shed much light on MB$k$RG,
viewed as a family of $(\textnormal{diam}(G)-1)$ resolving games played out on
a fixed graph $G$; in other words, viewing $O_{R,k}(G)$ as a function of $k$.

######  Theorem 2.13.

Let $k\in\mathbb{Z}^{+}$.

  * (a)

There exist graphs $G$ satisfying $O_{R,k}(G)=\mathcal{M}$ for $k\geq 1$.

  * (b)

There exist graphs $G$ satisfying $O_{R,k}(G)=\mathcal{N}$ for $k\geq 1$.

  * (c)

There exist graphs $G$ satisfying $O_{R,k}(G)=\mathcal{B}$ for $k\geq 1$.

  * (d)

There exists a graph $G$ such that $O_{R,1}(G)=\mathcal{N}$ and
$O_{R,k}(G)=\mathcal{M}$ for $k\geq 2$.

  * (e)

There exist graphs $G$ such that $O_{R,1}(G)=\mathcal{B}$ and
$O_{R,k}(G)=\mathcal{N}$ for $k\geq 2$.

  * (f)

There exist graphs $G$ such that $O_{R,1}(G)=\mathcal{B}$ and
$O_{R,k}(G)=\mathcal{M}$ for $k\geq 2$.

  * (g)

There exist 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\geq 3$.

###### Proof.

(a) Let $G$ be a tree obtained from $K_{1,\alpha}$, where $\alpha\geq 3$, by
subdividing exactly $(\alpha-2)$ edges once. Let
$\ell_{1},\ell_{2},\ldots,\ell_{\alpha}$ be the leaves and $v$ be the major
vertex of $G$ such that $d(v,\ell_{\alpha-1})=d(v,\ell_{\alpha})=1$ and
$d(v,\ell_{i})=2$ for each $i\in[\alpha-2]$, and let $s_{i}$ be the degree-two
vertex lying on the $v-\ell_{i}$ path for each $i\in[\alpha-2]$. Since
$\\{\\{\ell_{\alpha-1},\ell_{\alpha}\\}\\}\cup(\cup_{i=1}^{\alpha-2}\\{\\{s_{i},\ell_{i}\\}\\})$
is a pairing distance-$k$ resolving set of $G$ for each $k\in\mathbb{Z}^{+}$,
$O_{R,k}(G)=\mathcal{M}$ for all $k\geq 1$ by Observation 2.12(a).

(b) Let $G$ be a tree obtained from $K_{1,\alpha}$, where $\alpha\geq 4$, by
subdividing exactly $(\alpha-3)$ edges once. Let $v$ be the major vertex of
$G$ and let $\\{\ell_{1},\ell_{2},\ldots,\ell_{\alpha}\\}$ be the set of
leaves of $G$ such that
$d(v,\ell_{\alpha-2})=d(v,\ell_{\alpha-1})=d(v,\ell_{\alpha})=1$ and
$d(v,\ell_{i})=2$ for each $i\in[\alpha-3]$; further, for each
$i\in[\alpha-3]$, let $s_{i}$ be the degree-two vertex lying on the
$v-\ell_{i}$ path in $G$. We note that, for any distance-$k$ resolving set $R$
of $G$, $|R\cap\\{\ell_{\alpha-2},\ell_{\alpha-1},\ell_{\alpha}\\}|\geq 2$ by
Observation 2.6(b). Let
$X=\\{\\{\ell_{\alpha},\ell_{\alpha-1}\\}\\}\cup(\cup_{i=1}^{\alpha-3}\\{\\{s_{i},\ell_{i}\\}\\})$
and let $Z\subseteq V(G)$ with $|Z|=\alpha-2$ such that
$Z\cap\\{\ell_{\alpha},\ell_{\alpha-1}\\}\neq\emptyset$ and
$Z\cap\\{s_{i},\ell_{i}\\}\neq\emptyset$ for each $i\in[\alpha-3]$. Since
$Z\cup\\{\ell_{\alpha-2}\\}$ is a distance-$k$ resolving set of $G$ and $Z$
fails to form a distance-$k$ resolving set of $G$, $X$ is a quasi-pairing
distance-$k$ resolving set of $G$. By Observation 2.12(b),
$O_{R,k}(G)\in\\{\mathcal{M},\mathcal{N}\\}$. In the $B$-game, $B^{*}$ can
select two vertices in $\\{\ell_{\alpha},\ell_{\alpha-1},\ell_{\alpha-2}\\}$
after her second move; thus, $B^{*}$ wins the $B$-game. Therefore,
$O_{R,k}(G)=\mathcal{N}$ for all $k\geq 1$.

(c) Let $G=K_{1,\beta}$, where $\beta\geq 4$, be the star on ($\beta+1$)
vertices such that $L(G)=\cup_{i=1}^{\beta}\\{\ell_{i}\\}$ is the set of
leaves of $G$. Since $L(G)$ is a twin equivalence class of cardinality
$\beta\geq 4$, $O_{R,k}(G)=\mathcal{B}$ for all $k\geq 1$ by Corollary 2.8(a).

(d) Let $G$ be a tree obtained from a $3$-path given by $v_{1},v_{2},v_{3}$ by
joining exactly two leaves $\ell_{i}$ and $\ell^{\prime}_{i}$ to each $v_{i}$,
where $i\in[3]$. First, we show that $O_{R,1}(G)=\mathcal{N}$. Let $S$ be any
distance-$1$ resolving set of $G$; for each $i\in[3]$,
$S\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$ by Observation 2.6(b)
since $\ell_{i}$ and $\ell^{\prime}_{i}$ are twins in $G$. We may assume that
$S_{0}=\\{\ell_{1},\ell_{2},\ell_{3}\\}\subseteq S$ by relabeling the vertices
of $G$ if necessary. We note that, for any distinct $i,j\in[3]$,
$\textnormal{code}_{S_{0},1}(\ell^{\prime}_{i})=\textnormal{code}_{S_{0},1}(\ell^{\prime}_{j})$
and
$R_{1}\\{\ell^{\prime}_{i},\ell^{\prime}_{j}\\}=\\{v_{i},\ell^{\prime}_{i},v_{j},\ell^{\prime}_{j}\\}$;
thus,
$S\cap\\{v_{i},\ell^{\prime}_{i},v_{j},\ell^{\prime}_{j}\\}\neq\emptyset$. So,
$|S|\geq 5$, and thus $\dim_{1}(G)\geq 5$. Let
$X=\\{\\{v_{2},v_{3}\\}\\}\cup(\cup_{i=1}^{3}\\{\\{\ell_{i},\ell^{\prime}_{i}\\}\\})$
and let $Z\subseteq V(G)$ with $|Z|=4$ such that
$Z\cap\\{v_{2},v_{3}\\}\neq\emptyset$ and
$Z\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$ for each $i\in[3]$. Since
$Z\cup\\{v_{1}\\}$ is a minimum distance-$1$ resolving set of $G$, $X$ is a
quasi-pairing distance-$1$ resolving set of $G$. In the $B$-game of the
MB$1$RG, $B^{*}$ wins since $M^{*}$ can occupy at most 4 vertices in the
course of the game and $\dim_{1}(G)=5$. Thus, $O_{R,1}(G)=\mathcal{N}$ by
Observation 2.12(b).

Second, we show that $O_{R,k}(G)=\mathcal{M}$ for all $k\geq 2$. Since
$\cup_{i=1}^{3}\\{\\{\ell_{i},\ell^{\prime}_{i}\\}\\}$ is a pairing
distance-$k$ resolving set of $G$ for all $k\geq 2$, $O_{R,k}(G)=\mathcal{M}$
for all $k\geq 2$ by Observation 2.12(a).

(e) Let $G$ be a tree obtained from an $\alpha$-path
$v_{1},v_{2},\ldots,v_{\alpha}$, where $\alpha\geq 3$, by attaching exactly
three leaves
$\ell_{\alpha},\ell^{\prime}_{\alpha},\ell^{\prime\prime}_{\alpha}$ to
$v_{\alpha}$ and attaching exactly two leave $\ell_{i}$ and
$\ell^{\prime}_{i}$ to each $v_{i}$, where $i\in[\alpha-1]$.

First, we show that $O_{R,1}(G)=\mathcal{B}$. Let $S$ be any distance-$1$
resolving set of $G$. By Observation 2.6(b),
$|S\cap\\{\ell_{\alpha},\ell^{\prime}_{\alpha},\ell^{\prime\prime}_{\alpha}\\}|\geq
2$ and $|S\cap\\{\ell_{i},\ell^{\prime}_{i}\\}|\geq 1$ for each
$i\in[\alpha-1]$. By relabeling the vertices of $G$ if necessary, we may
assume that
$S_{0}=(\cup_{i=1}^{\alpha-1}\\{\ell^{\prime}_{i}\\})\cup\\{\ell^{\prime}_{\alpha},\ell^{\prime\prime}_{\alpha}\\}\subseteq
S$. Note that, for any distinct $i,j\in[\alpha]$,
$\textnormal{code}_{S_{0},1}(\ell_{i})=\textnormal{code}_{S_{0},1}(\ell_{j})$
and $R_{1}\\{\ell_{i},\ell_{j}\\}=\\{v_{i},\ell_{i},v_{j},\ell_{j}\\}$; thus,
$|S\cap\\{v_{i},\ell_{i},v_{j},\ell_{j}\\}|\geq 1$. So, $|S|\geq 2\alpha$ and
hence $\dim_{1}(G)\geq 2\alpha$. Since $\dim_{1}(G)\geq
2\alpha\geq\lceil\frac{3\alpha+1}{2}\rceil+1=\lceil\frac{|V(G)|}{2}\rceil+1$
for $\alpha\geq 3$, $O_{R,1}(G)=\mathcal{B}$ by Observation 2.9(b).

Second, we show that $O_{R,k}(G)=\mathcal{N}$ for all $k\geq 2$. Let $k\geq
2$. Let $X=\cup_{i=1}^{\alpha}\\{\\{\ell_{i},\ell^{\prime}_{i}\\}\\}$ and let
$Z\subseteq V(G)$ with $|Z|=\alpha$ such that
$Z\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$ for each $i\in[\alpha]$.
Since $Z\cup\\{\ell^{\prime\prime}_{\alpha}\\}$ forms a minimum distance-$k$
resolving set of $G$, $X$ is a quasi-pairing distance-$k$ resolving set of
$G$. By Observation 2.12(b), $O_{R,k}(G)\in\\{\mathcal{M},\mathcal{N}\\}$.
Note that, in the $B$-game of the MB$k$RG, $B^{*}$ has a winning strategy
since $B^{*}$ can occupy two vertices of
$\\{\ell_{\alpha},\ell^{\prime}_{\alpha},\ell^{\prime\prime}_{\alpha}\\}$
after her second move, and thus preventing $M^{*}$ from occupying vertices
that form a distance-$k$ resolving set of $G$. So, $O_{R,k}(G)=\mathcal{N}$
for all $k\geq 2$.

(f) Let $G$ be a tree obtained from an $\alpha$-path
$v_{1},v_{2},\ldots,v_{\alpha}$, where $\alpha\geq 4$, by joining exactly two
leaves $\ell_{i}$ and $\ell^{\prime}_{i}$ to each $v_{i}$, where
$i\in[\alpha]$.

First, we show that $O_{R,1}(G)=\mathcal{B}$. For each $i\in[\alpha]$ and for
any distance-$1$ resolving set $S$ of $G$,
$S\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$ by Observation 2.6(b). We
may assume that $S^{*}=\cup_{i=1}^{\alpha}\\{\ell_{i}\\}\subseteq S$ by
relabeling the vertices of $G$ if necessary. We note that, for any distinct
$i,j\in[\alpha]$,
$\textnormal{code}_{S^{*},1}(\ell^{\prime}_{i})=\textnormal{code}_{S^{*},1}(\ell^{\prime}_{j})$
and
$R_{1}\\{\ell^{\prime}_{i},\ell^{\prime}_{j}\\}=\\{v_{i},\ell^{\prime}_{i},v_{j},\ell^{\prime}_{j}\\}$;
thus,
$S\cap\\{v_{i},\ell^{\prime}_{i},v_{j},\ell^{\prime}_{j}\\}\neq\emptyset$. So,
$|S|\geq 2\alpha-1$, and thus $\dim_{1}(G)\geq 2\alpha-1$. Since
$\dim_{1}(G)\geq
2\alpha-1\geq\lceil\frac{3\alpha}{2}\rceil+1=\lceil\frac{|V(G)|}{2}\rceil+1$
for $\alpha\geq 4$, $O_{R,1}(G)=\mathcal{B}$ by Observation 2.9(b).

Second, we show that $O_{R,k}(G)=\mathcal{M}$ for all $k\geq 2$. Since
$\cup_{i=1}^{\alpha}\\{\\{\ell_{i},\ell^{\prime}_{i}\\}\\}$ is a pairing
distance-$2$ resolving set of $G$, $O_{R,2}(G)=\mathcal{M}$ by Observation
2.12(a). By Proposition 2.4, $O_{R,k}(G)=\mathcal{M}$ for all $k\geq 2$.

(g) Let $G$ be the graph in Figure 1, where $\alpha\geq 2$. We note the
following: (i) for any minimum distance-$k$ resolving set $S$ of $G$ and for
each $i\in[\alpha]$, $S\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$ and
$S\cap\\{s_{i},s^{\prime}_{i}\\}\neq\emptyset$ by Observation 2.6(b); (ii) if
$S_{0}=\cup_{i=1}^{\alpha}\\{\ell_{i},s_{i}\\}\subseteq S$, then
$\textnormal{code}_{S_{0},k}(\ell^{\prime}_{j})=\textnormal{code}_{S_{0},k}(s^{\prime}_{j})$
for each $k\geq 1$ and for each $j\in[\alpha]$; (iii) for each $i\in[\alpha]$,
$R_{1}\\{\ell^{\prime}_{i},s^{\prime}_{i}\\}=\\{\ell^{\prime}_{i},s^{\prime}_{i},x_{i}\\}$;
(iv) for each $i\in[\alpha]$,
$R_{2}\\{\ell^{\prime}_{i},s^{\prime}_{i}\\}=\\{\ell^{\prime}_{i},s^{\prime}_{i},x_{i},y\\}$;
(v) for each $i\in[\alpha]$ and for each $k\geq 3$,
$R_{k}\\{\ell^{\prime}_{i},s^{\prime}_{i}\\}\supseteq\\{\ell^{\prime}_{i},s^{\prime}_{i},x_{i},y,z\\}$.
Let
$W=\cup_{i=1}^{\alpha}\\{\\{\ell_{i},\ell^{\prime}_{i}\\},\\{s_{i},s^{\prime}_{i}\\}\\}$.

First, we show that $O_{R,1}(G)=\mathcal{B}$. In the $M$-game, $B^{*}$ can
choose exactly one vertex of each pair in $W$ and at least one vertex in
$\cup_{i=1}^{\alpha}\\{x_{i}\\}$. By relabeling the vertices of $G$ if
necessary, we may assume that $B^{*}$ chose the vertices in
$\\{x_{j}\\}\cup(\cup_{i=1}^{\alpha}\\{\ell^{\prime}_{i},s^{\prime}_{i}\\})$
after her $(2\alpha+1)$st move. Since all vertices in
$\\{\ell^{\prime}_{j},s^{\prime}_{j},x_{j}\\}$, for some $j\in[\alpha]$, are
occupied by $B^{*}$, (iii) implies that $M^{*}$ fails to occupy vertices that
form a distance-$1$ resolving set of $G$ in the $M$-game of the MB$1$RG. Thus,
$O_{R,1}(G)=\mathcal{B}$.

Second, we show that $O_{R,2}(G)=\mathcal{N}$. Let $U\subseteq V(G)$ with
$|U|=2\alpha$ such that $U\cap\\{\ell_{i},\ell^{\prime}_{i}\\}\neq\emptyset$
and $U\cap\\{s_{i},s^{\prime}_{i}\\}\neq\emptyset$ for each $i\in[\alpha]$.
Since $U\cup\\{y\\}$ is a minimum distance-$2$ resolving set of $G$, $W$ is a
quasi-pairing distance-$2$ resolving set of $G$. By Observation 2.12(b),
$O_{R,2}(G)\in\\{\mathcal{M},\mathcal{N}\\}$. In the $B$-game, $B^{*}$ can
select the vertex $y$ and exactly one vertex of each pair in $W$; we may
assume that $B^{*}$ chose the vertices in
$\\{y\\}\cup(\cup_{i=1}^{\alpha}\\{\ell^{\prime}_{i},s^{\prime}_{i}\\})$ after
her $(2\alpha+1)$st move. In order for $M^{*}$ to occupy vertices that form a
distance-$2$ resolving set of $G$ in the $B$-game, (iv) implies that $M^{*}$
must select all vertices in $\cup_{i=1}^{\alpha}\\{x_{i}\\}$ in addition to
the vertices in $\cup_{i=1}^{\alpha}\\{\ell_{i},s_{i}\\}$, but this is
impossible since $\alpha\geq 2$ and $B^{*}$ can select at least one vertex in
$\cup_{i=1}^{\alpha}\\{x_{i}\\}$ in her $(2\alpha+2)$nd move. So, $B^{*}$ wins
the $B$-game of the MB$2$RG. Thus, $O_{R,2}(G)=\mathcal{N}$.

Third, we show that $O_{R,k}(G)=\mathcal{M}$ for $k\geq 3$. Since
$\\{\\{y,z\\}\\}\cup W$ is a pairing distance-$k$ resolving set of $G$ for
$k\geq 3$, $O_{R,k}(G)=\mathcal{M}$ for all $k\geq 3$ by Observation 2.12(a).
∎

$v_{1}$$v_{2}$$v_{\alpha}$$\ell_{1}$$\ell^{\prime}_{1}$$s_{1}$$s^{\prime}_{1}$$x_{1}$$\ell_{2}$$\ell^{\prime}_{2}$$s_{2}$$s^{\prime}_{2}$$x_{2}$$\ell_{\alpha}$$\ell^{\prime}_{\alpha}$$s_{\alpha}$$s^{\prime}_{\alpha}$$x_{\alpha}$$y$$z$
Figure 1: 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\geq 3$, where
$\alpha\geq 2$.

##  3 Time to win or lose the MB$k$RG, and some graph classes

In this section, we consider the outcome of the MB$k$RG as well as the minimum
number of steps needed to reach the outcome of the MB$k$RG on some graph
classes. Taking into consideration of Proposition 2.4 and Corollary 2.5, we
make the following observation.

######  Observation 3.1.

Let $k\in\mathbb{Z}^{+}$ and $G$ be a connected graph of order $n\geq 2$.

  * (a)

If $O_{R,k}(G)=\mathcal{M}$, then $\dim_{k}(G)\leq M_{R,k}(G)\leq
M^{\prime}_{R,k}(G)\leq\lfloor\frac{n}{2}\rfloor$, $M_{R,k+1}(G)\leq
M_{R,k}(G)$ and $M^{\prime}_{R,k+1}(G)\leq M^{\prime}_{R,k}(G)$.

  * (b)

If $O_{R,k}(G)=\mathcal{B}$, then $B^{\prime}_{R,k}(G)\leq
B_{R,k}(G)\leq\lfloor\frac{n}{2}\rfloor$; moreover, for $k>1$, $B_{R,k}(G)\geq
B_{R,k-1}(G)$ and $B^{\prime}_{R,k}(G)\geq B^{\prime}_{R,k-1}(G)$.

  * (c)

If $\textnormal{diam}(G)\in\\{1,2\\}$ or $k\geq\textnormal{diam}(G)-1$, then
$M_{R,k}(G)=M_{R}(G)$ and $M^{\prime}_{R,k}(G)=M^{\prime}_{R}(G)$ if
$O_{R}(G)=\mathcal{M}$, and $B_{R,k}(G)=B_{R}(G)$ and
$B^{\prime}_{R,k}(G)=B^{\prime}_{R}(G)$ if $O_{R}(G)=\mathcal{B}$.

  * (d)

If $X$ is a pairing distance-$k$ resolving set of $G$ with $|\bigcup
X|=2\dim_{k}(G)$, then $M_{R,k}(G)=M^{\prime}_{R,k}(G)=\dim_{k}(G)$.

  * (e)

If $X$ is a quasi-pairing distance-$k$ resolving set of $G$ with $|\bigcup
X|=2(\dim_{k}(G)-1)$ and $O_{R,k}(G)=\mathcal{N}$, then
$N_{R,k}(G)=\dim_{k}(G)$.

Next, we examine the MB$k$RG on some graph classes. We first consider the
Petersen graph and complete multipartite graphs.

######  Example 3.2.

Let $k\in\mathbb{Z}^{+}$.

(a) Let $\mathcal{P}$ denote the Petersen graph. It was shown in [18] that
$O_{R}(\mathcal{P})=\mathcal{M}$ and
$M_{R}(\mathcal{P})=3=M^{\prime}_{R}(\mathcal{P})$. Since
$\textnormal{diam}(\mathcal{P})=2$, Corollary 2.5(a) and Observation 3.1(c)
imply that $O_{R,k}(\mathcal{P})=\mathcal{M}$ and
$M_{R,k}(\mathcal{P})=3=M^{\prime}_{R,k}(\mathcal{P})$ for all $k$.

(b) For $m\geq 2$, let $G=K_{a_{1},a_{2},\ldots,a_{m}}$ be a complete multi-
partite graph of order $\sum_{i=1}^{m}a_{i}$, and let $s$ be the number of
partite sets of $G$ consisting of exactly one element. Since
$\textnormal{diam}(G)\leq 2$, Corollary 2.5(a) implies $O_{R,k}(G)=O_{R}(G)$
for all $k$, and $O_{R}(G)$ was determined in [18]. So,

$O_{R,k}(G)=\left\\{\begin{array}[]{ll}\mathcal{B}&\mbox{if }s\geq 4,\mbox{ or
}a_{i}\geq 4\mbox{ for some }i\in[m],\\\ &\mbox{ or }s=a_{i}=3\mbox{ for some
}i\in[m],\\\ &\mbox{ or }a_{i}=a_{j}=3\mbox{ for distinct }i,j\in[m],\\\
\mathcal{N}&\mbox{if }s=3\mbox{ and }a_{i}\leq 2\mbox{ for each }i\in[m],\\\
&\mbox{ or }s\leq 2,a_{i}\leq 3\mbox{ for each }i\in[m]\mbox{ and
}a_{j}\\!=\\!3\mbox{ for exactly one }j\in[m],\\\ \mathcal{M}&\mbox{if }s\leq
2\mbox{ and }a_{i}\leq 2\mbox{ for each }i\in[m].\end{array}\right.$

Moreover, we have the following: (i) if $O_{R,k}(G)=\mathcal{M}$, then
$M_{R,k}(G)=M^{\prime}_{R,k}(G)=\dim(G)$ by Theorem 4.12 of [18] and
Observation 3.1(c); (ii) if $O_{R,k}(G)=\mathcal{B}$, then
$B_{R,k}(G)=B^{\prime}_{R,k}(G)=2$ by Proposition 3.2 of [18] and Observation
3.1(c); (iii) if $O_{R,k}(G)=\mathcal{N}$, then $N_{R,k}(G)=\dim(G)$ and
$N^{\prime}_{R,k}(G)=2$. To see (iii), we note that if
$O_{R,k}(G)=\mathcal{N}$, then $G$ has exactly one twin equivalence class of
cardinality $3$, say $Q$, and $G$ admits a quasi-pairing distance-$k$
resolving set, say $X$, with $|\bigcup X|=2(\dim_{k}(G)-1)$. In the $M$-game,
$N_{R,k}(G)=\dim(G)$ by Observations 2.3(a) and 3.1(e). In the $B$-game,
$N^{\prime}_{R,k}(G)=2$ by Observation 2.6(b) and the fact that $B^{*}$ can
occupy $2$ vertices of $Q$ after her second move.

Next, we consider cycles. It was obtained in [18] that
$O_{R}(C_{n})=\mathcal{M}$ for $n\geq 4$. We recall some terminology.
Following [4], let $M$ be a set of at least two vertices of $C_{n}$, let
$u_{i}$ and $u_{j}$ be distinct vertices of $M$, and let $P$ and $P^{\prime}$
denote the two distinct $u_{i}-u_{j}$ paths determined by $C_{n}$. If either
$P$ or $P^{\prime}$, say $P$, contains only two vertices of $M$ (namely,
$u_{i}$ and $u_{j}$), then we refer to $u_{i}$ and $u_{j}$ as _neighboring
vertices_ of $M$ and the set of vertices of $V(P)-\\{u_{i},u_{j}\\}$ as the
_gap_ of $M$ (determined by $u_{i}$ and $u_{j}$). The two gaps of $M$
determined by a vertex of $M$ and its two neighboring vertices of $M$ are
called _neighboring gaps_. Note that, $M$ has $r$ gaps if $|M|=r$, where some
of the gaps may be empty. The following lemma and its proof are adapted from
[4].

######  Lemma 3.3.

Let $S\subseteq V(C_{n})$, where $n\geq 5$. Suppose $S$ satisfies the
following two conditions: (1) every gap of $S$ contains at most $3$ vertices,
and at most one gap of $S$ contains $3$ vertices; (2) if a gap of $S$ contains
at least $2$ vertices, then its neighboring gaps contain at most $1$ vertex.
Then $S$ is a distance-$1$ resolving set of $C_{n}$.

###### Proof.

Let $S\subseteq V(C_{n})$ satisfy the conditions of the present lemma, where
$n\geq 5$. Let $C_{n}$ be given by $u_{0},u_{1},\ldots,u_{n-1},u_{0}$ and let
$v\in V(C_{n})-S$. Let ${\bf{2}}_{|S|}$ denote the $|S|$-vector with $2$ on
each entry of $\textnormal{code}_{S,1}(\cdot)$, and all subscripts in this
proof are taken modulo $n$.

First, suppose $v=u_{i}$ belongs to a gap of size $1$ of $S$. Then
$W_{0}=\\{u_{i-1},u_{i+1}\\}\subseteq S$ and
$\textnormal{code}_{W_{0},1}(u_{i})=(1,1)\neq\textnormal{code}_{W_{0},1}(u_{j})$
for each $u_{j}\in V(C_{n})-(S\cup\\{u_{i}\\})$ since $u_{j}$ cannot be
adjacent to both $u_{i-1}$ and $u_{i+1}$ in $C_{n}$.

Second, suppose $v=u_{i}$ belongs to a gap of size $2$ of $S$ such that
$\\{u_{i},u_{i+1}\\}\cap S=\emptyset$ or $\\{u_{i-1},u_{i}\\}\cap
S=\emptyset$, say the former. Let $W_{1}=\\{u_{i-1},u_{i+2}\\}\subseteq S$. If
$n=5$, then $\\{\textnormal{code}_{W_{1},1}(u_{j}):u_{j}\in
V(C_{5})-W_{1}\\}=\\{(1,1),(1,2),(2,1)\\}$. So, suppose $n\geq 6$. By the
condition (2) of the present lemma, $\\{u_{i-2},u_{i-3}\\}\cap
S\neq\emptyset$. If $u_{i-2}\in S$, then
$\textnormal{code}_{W_{1},1}(u_{i})=(1,2)\neq\textnormal{code}_{W_{1},1}(u_{j})$
for each $u_{j}\in V(C_{n})-(S\cup\\{u_{i}\\})$ since $u_{j}$ cannot be
adjacent to $u_{i-1}$ in $C_{n}$. If $u_{i-2}\not\in S$ and $u_{i-3}\in S$,
then we have the following: (i)
$\textnormal{code}_{W_{1},1}(u_{i})=\textnormal{code}_{W_{1},1}(u_{i-2})=(1,2)\neq\textnormal{code}_{W_{1},1}(u_{j})$
for each $u_{j}\in V(C_{n})-(S\cup\\{u_{i},u_{i-2}\\})$ since $u_{j}$ is not
adjacent to $u_{i-1}$ in $C_{n}$; (ii)
$\textnormal{code}_{S,1}(u_{i})\neq\textnormal{code}_{S,1}(u_{i-2})$ since
$d_{1}(u_{i},u_{i-3})=2>1=d_{1}(u_{i-2},u_{i-3})$.

Third, suppose $v=u_{i}$ belongs to a gap of size $3$ of $S$. If
$\\{u_{i-1},u_{i},u_{i+1}\\}\cap S=\emptyset$, then
$\textnormal{code}_{S,1}(u_{i})={\bf{2}}_{|S|}\neq\textnormal{code}_{S,1}(u_{j})$
for each $u_{j}\in V(C_{n})-(S\cup\\{u_{i}\\})$ since $u_{j}$ is adjacent to
at least one vertex of $S$. Now, suppose $\\{u_{i},u_{i+1},u_{i+2}\\}\cap
S=\emptyset$ or $\\{u_{i-2},u_{i-1},u_{i}\\}\cap S=\emptyset$, say the former;
then $W=\\{u_{i-1},u_{i+3}\\}\subseteq S$. If $n=5$, then
$\\{\textnormal{code}_{W,1}(u_{j}):u_{j}\in
V(C_{5})-W\\}=\\{(1,2),(2,1),(2,2)\\}$. If $n=6$, then
$\\{\textnormal{code}_{W,1}(u_{j}):u_{j}\in
V(C_{6})-W\\}=\\{(1,1),(1,2),(2,1),(2,2)\\}$. So, suppose $n\geq 7$. Note that
$\\{u_{i-2},u_{i-3}\\}\cap S\neq\emptyset$ by the condition (2) of the present
lemma. If $u_{i-2}\in S$, then
$\textnormal{code}_{W,1}(u_{i})=(1,2)\neq\textnormal{code}_{W,1}(u_{j})$ for
each $u_{j}\in V(C_{n})-(S\cup\\{u_{i}\\})$ since $u_{j}$ is not adjacent to
$u_{i-1}$ in $C_{n}$. If $u_{i-2}\not\in S$ and $u_{i-3}\in S$, then
$\textnormal{code}_{W,1}(u_{i})=\textnormal{code}_{W,1}(u_{i-2})=(1,2)\neq\textnormal{code}_{W,1}(u_{j})$
for each $u_{j}\in V(C_{n})-(S\cup\\{u_{i},u_{i-2}\\})$ and
$d_{1}(u_{i},u_{i-3})=2>1=d_{1}(u_{i-2},u_{i-3})$; thus,
$\textnormal{code}_{S,1}(u_{i})\neq\textnormal{code}_{S,1}(u_{j})$ for each
$u_{j}\in V(C_{n})-(S\cup\\{u_{i}\\})$. ∎

As a generalization of Lemma 3.3, we state the following result without
providing a detailed proof, where its proof for $k=1$ is given in Lemma 3.3.
The proof for the converse of Lemma 3.4 is provided in [10].

######  Lemma 3.4.

Let $k\in\mathbb{Z}^{+}$ and $S\subseteq V(C_{n})$, where $n\geq 2k+3$.
Suppose $S$ satisfies the following two conditions: (1) every gap of $S$
contains at most $(2k+1)$ vertices, and at most one gap of $S$ contains
$(2k+1)$ vertices; (2) if a gap of $S$ contains at least $(k+1)$ vertices,
then its neighboring gaps contain at most $k$ vertices. Then $S$ is a
distance-$k$ resolving set of $C_{n}$.

######  Proposition 3.5.

Let $k\in\mathbb{Z}^{+}$ and $n\geq 3$. Then

$O_{R,k}(C_{n})=\left\\{\begin{array}[]{ll}\mathcal{N}&\mbox{if $n=3$
and~{}}k\geq 1,\\\ \mathcal{M}&\mbox{if $n\geq 4$ is even and~{}}k\geq 1,\\\
\mathcal{M}&\mbox{if $n\geq 5$ is odd and~{}}k\geq 2.\end{array}\right.$

###### Proof.

Let $k\in\mathbb{Z}^{+}$. Let $C_{n}$ be given by
$u_{1},u_{2},\ldots,u_{n},u_{1}$, where $n\geq 3$. Note that
$O_{R,k}(C_{3})=\mathcal{N}$ by Example 3.2(b). If $n=4$, then
$\\{\\{u_{1},u_{3}\\},\\{u_{2},u_{4}\\}\\}$ is a pairing distance-$k$
resolving set of $C_{4}$; thus, $O_{R,k}(C_{4})=\mathcal{M}$ by Observation
2.12(a). So, suppose $n\geq 5$.

If $n=2x$ ($x\geq 3$), let $X=\cup_{i=1}^{x}\\{\\{u_{2i-1},u_{2i}\\}\\}$ and
$S$ be the set of vertices that are selected by $M^{*}$ over the course of the
MB$1$RG such that $M^{*}$ selects exactly one vertex in
$\\{u_{2i-1},u_{2i}\\}$ for each $i\in[x]$. Then we have the following: (i)
every gap of $S$ contains at most $2$ vertices; (ii) if a gap of $S$ contains
$2$ vertices, then its neighboring gaps contain at most $1$ vertex. By Lemma
3.3, $S$ is a distance-$1$ resolving set of $C_{n}$. Since $X$ is a pairing
distance-$1$ resolving set of $C_{n}$, $O_{R,1}(C_{n})=\mathcal{M}$ by
Observation 2.12(a). By Proposition 2.4, $O_{R,k}(C_{n})=\mathcal{M}$ for even
$n\geq 6$ and for $k\geq 1$.

If $n=2x+1$ ($x\geq 2$), let $Y=\cup_{i=1}^{x}\\{\\{u_{2i-1},u_{2i}\\}\\}$. In
the $B$-game of the MB$k$RG, suppose $B^{*}$ selects $u_{n}=u_{2x+1}$ (by
relabeling the vertices of $C_{n}$ if necessary) after her first move and let
$S^{\prime}$ be the set of vertices that are selected by $M^{*}$ such that
$M^{*}$ selects exactly one vertex in $\\{u_{2i-1},u_{2i}\\}$ for each
$i\in[x]$. Then we have the following: (i) at most one gap of $S^{\prime}$
contains $3$ vertices (when $B^{*}$ is able to select all vertices in
$\\{u_{1},u_{n-1},u_{n}\\}$ over the course of the MB$k$RG) and all other gaps
of $S^{\prime}$ contain at most $2$ vertices; (ii) if a gap of $S^{\prime}$
contains $3$ vertices, then its neighboring gaps contain at most $1$ vertex.
By Lemma 3.4, $S^{\prime}$ is a distance-$2$ resolving set of $C_{n}$. Since
$Y$ is a pairing distance-$2$ resolving set of $C_{n}$,
$O_{R,2}(C_{n})=\mathcal{M}$ by Observation 2.12(a). By Proposition 2.4,
$O_{R,k}(C_{n})=\mathcal{M}$ for odd $n\geq 5$ and for $k\geq 2$. ∎

######  Remark 3.6.

Let $C_{n}$ be given by $u_{1},u_{2},\ldots,u_{n},u_{1}$. We consider the
$B$-game of the MB$1$RG.

(1) We show that $O_{R,1}(C_{5})=\mathcal{M}$. Without loss of generality,
suppose $B^{*}$ selects $u_{5}$ on her first move. Then $M^{*}$ selects
$u_{4}$ on his first move and exactly one vertex in $\\{u_{2},u_{3}\\}$ on his
second move. Since the vertices selected by $M^{*}$ form a distance-$1$
resolving set of $C_{5}$, $O_{R,1}(C_{5})=\mathcal{M}$.

(2) We show that $O_{R,1}(C_{7})=\mathcal{M}$. Let $S$ be the set of vertices
that are selected by $M^{*}$ over the course of the game. Without loss of
generality, suppose $B^{*}$ selects $u_{7}$ on her first move. Then $M^{*}$
selects $u_{6}$ on his first move. If $B^{*}$ selects a vertex in
$\\{u_{1},u_{2}\\}$ on her second move, then $M^{*}$ selects $u_{3}$ on his
second move and exactly one vertex of $\\{u_{4},u_{5}\\}$ on his third move.
If $B^{*}$ selects $u_{3}$ on her second move, then $M^{*}$ selects $u_{4}$ on
his second move and exactly one vertex of $\\{u_{1},u_{2}\\}$ on his third
move. If $B^{*}$ selects $u_{4}$ on her second move, then $M^{*}$ selects
$u_{3}$ on his second move and exactly one vertex of $\\{u_{1},u_{5}\\}$ on
his third move. If $B^{*}$ selects $u_{5}$ on her second move, then $M^{*}$
selects $u_{4}$ on his second move and exactly one vertex of
$\\{u_{1},u_{2},u_{3}\\}$ on his third move. In each case, $S$ satisfies the
conditions of Lemma 3.3; thus, $S$ is a distance-$1$ resolving set of $C_{7}$
and $O_{R,1}(C_{7})=\mathcal{M}$.

######  Conjecture 3.7.

In addition to $C_{5}$ and $C_{7}$, we find that $O_{R,1}(C_{9})=\mathcal{M}$
through explicit computation. We further conjecture that
$O_{R,1}(C_{n})=\mathcal{M}$ for all odd $n\geq 5$, but an argument for the
general (odd) $n$ eludes us.

Next, we consider wheel graphs. The _join_ of two graphs $G$ and $H$, denoted
by $G+H$, is the graph obtained from the disjoint union of $G$ and $H$ by
adding additional edges between each vertex of $G$ and each vertex of $H$.
Since $\textnormal{diam}(G+H)\leq 2$, $O_{R,k}(G+H)=O_{R}(G+H)$, for all
$k\in\mathbb{Z}^{+}$, by Corollary 2.5(a). Let $d_{G}(w_{i},w_{j})$ denote the
distance between the vertices $w_{i}$ and $w_{j}$ in a graph $G$, and let
$d_{G,k}(w_{i},w_{j})$ denote $d_{k}(w_{i},w_{j})$ in $G$.

For the wheel graph $C_{n}+K_{1}$, let $V(K_{1})=\\{v\\}$ and let $C_{n}$ be
given by $u_{1},u_{2},\ldots,u_{n},u_{1}$ such that $v$ is adjacent to each
$u_{i}$, where $i\in[n]$, in $C_{n}+K_{1}$. Let $k\in\mathbb{Z}^{+}$. If
$n=3$, then $O_{R,k}(C_{3}+K_{1})=O_{R,k}(K_{4})=\mathcal{B}$ by Proposition
2.8(a). If $n=4$, then $\\{\\{u_{1},u_{3}\\},\\{u_{2},u_{4}\\}\\}$ is a
pairing distance-$k$ resolving set of $C_{4}+K_{1}$. If $n=5$, then
$\\{\\{u_{1},u_{2}\\},\\{u_{3},u_{4}\\},\\{u_{5},v\\}\\}$ is a pairing
distance-$k$ resolving set of $C_{5}+K_{1}$. So,
$O_{R,k}(C_{4}+K_{1})=O_{R,k}(C_{5}+K_{1})=\mathcal{M}$, for all $k\geq 1$, by
Observation 2.12(a). For $n\geq 6$, let $S$ be the set of vertices lying on
$C_{n}$ that are selected by $M^{*}$ over the course of MB$k$RG; notice that
$\textnormal{code}_{S,k}(v)=(1,1,\ldots,1)\neq\textnormal{code}_{S,k}(u_{i})$
for each $i\in[n]$. Since
$d_{C_{n}+K_{1}}(u_{i},u_{j})=d_{C_{n},1}(u_{i},u_{j})$ for $i,j\in[n]$, the
same method of proof for Proposition 3.5 and Remark 3.6 provides the following
result.

######  Corollary 3.8.

Let $k\in\mathbb{Z}^{+}$ and $n\geq 3$. Then (i)
$O_{R,k}(C_{3}+K_{1})=O_{R}(C_{3}+K_{1})=\mathcal{B}$; (ii) if
$n\in\\{4,5,6,7\\}$ or $n\geq 8$ is even, then
$O_{R,k}(C_{n}+K_{1})=O_{R}(C_{n}+K_{1})=\mathcal{M}$; (iii) if $n\geq 9$ is
odd, then
$O_{R,k}(C_{n}+K_{1})=O_{R}(C_{n}+K_{1})\in\\{\mathcal{M},\mathcal{N}\\}$
(because $M^{*}$ has a winning strategy in the $M$-game of the MB$k$RG).

Next, we consider trees with some restrictions. We recall some terminology and
notations. Fix a tree $T$. A vertex $\ell$ of degree one is called a _terminal
vertex_ of a major vertex $v$ if $d(\ell,v)<d(\ell,w)$ for every other major
vertex $w$ in $T$. The _terminal degree_ , $ter_{T}(v)$, of a major vertex $v$
is the number of terminal vertices of $v$ in $T$, and an _exterior major
vertex_ is a major vertex with positive terminal degree. Let $M(T)$ be the set
of exterior major vertices of $T$. For each $i\in[3]$, let $M_{i}(T)=\\{w\in
M(T):ter_{T}(w)=i\\}$, and let $M_{4}(T)=\\{w\in M(T):ter_{T}(w)\geq 4\\}$;
note that $M(T)=\cup_{j=1}^{4}M_{j}(T)$.

######  Theorem 3.9.

Let $k\in\mathbb{Z}^{+}$ and $T$ be a tree that is not a path. Further,
suppose that $T$ contains neither a degree-two vertex nor a major vertex with
terminal degree zero. Then

$O_{R,k}(T)=\left\\{\begin{array}[]{ll}\mathcal{B}&\mbox{if }|M_{4}(T)|\geq
1\mbox{ or }|M_{3}(T)|\geq 2\mbox{ for all }k\geq 1,\\\ {}&\mbox{ or
}M_{4}(T)=\emptyset,|M_{3}(T)|=1,|M_{2}(T)|\geq 2\mbox{ and }k=1,\\\ {}&\mbox{
or }M_{4}(T)=M_{3}(T)=\emptyset,|M_{2}(T)|\geq 4\mbox{ and }k=1,\\\
\mathcal{N}&\mbox{if
}M_{4}(T)=\emptyset,|M_{3}(T)|=1,|M_{2}(T)|\in\\{0,1\\}\mbox{ and }k=1,\\\
{}&\mbox{ or }M_{4}(T)=\emptyset\mbox{ and }|M_{3}(T)|=1\mbox{ for all }k\geq
2,\\\ {}&\mbox{ or }M_{4}(T)=M_{3}(T)=\emptyset,|M_{2}(T)|=3\mbox{ and
}k=1,\\\ \mathcal{M}&\mbox{if }M_{4}(T)=M_{3}(T)=\emptyset,|M_{2}(T)|=2\mbox{
and }k=1,\\\ {}&\mbox{ or }M_{4}(T)=M_{3}(T)=\emptyset\mbox{ and
}M_{2}(T)\neq\emptyset\mbox{ for all }k\geq 2.\end{array}\right.$

###### Proof.

Let $k\in\mathbb{Z}^{+}$, and let $T$ be a tree as described in the statement
of the present theorem. Then each vertex of $T$ is either a leaf or an
exterior major vertex. Let $M_{1}(T)=\\{u_{1},u_{2},\ldots,u_{x}\\}$ and
$M^{\prime}(T)=\cup_{i=2}^{4}M_{i}(T)=\\{v_{1},v_{2},\ldots,v_{z}\\}$, where
$x\geq 0$ and $z\geq 1$. If $x\geq 1$, then, for each $j\in[x]$, let $m_{j}$
be the terminal vertex of $u_{j}$; notice that $m_{j}u_{j}\in E(T)$. For each
$i\in[z]$, let $ter_{T}(v_{i})=\sigma_{i}\geq 2$ and let
$\\{\ell_{i,1},\ldots,\ell_{i,\sigma_{i}}\\}$ be the set of terminal vertices
of $v_{i}$ in $T$.

First, suppose $|M_{4}(T)|\geq 1$; then Corollary 2.8(a) implies that
$O_{R,k}(T)=\mathcal{B}$ for all $k\geq 1$. Second, suppose $|M_{3}(T)|\geq
2$; then Corollary 2.8(b) implies that $O_{R,k}(T)=\mathcal{B}$ for all $k\geq
1$.

Third, suppose that $M_{4}(T)=\emptyset$ and $|M_{3}(T)|=1$; then
$z=1+|M_{2}(T)|$. We may assume that $ter_{T}(v_{z})=3$ by relabeling the
vertices of $T$ if necessary. If $z=1$ (i.e., $M_{2}(T)=\emptyset$), then
$T=K_{1,3}$ and $O_{R,k}(T)=\mathcal{N}$ for all $k\geq 1$ by Example 3.2(b).

Now, suppose that $z\geq 2$ (i.e., $M_{2}(T)\neq\emptyset$); then
$ter_{T}(v_{i})=2$ for each $i\in[z-1]$. For any minimum distance-$k$
resolving set $W$ of $T$, Observation 2.6(b) implies that
$|W\cap\\{\ell_{z,1},\ell_{z,2},\ell_{z,3}\\}|\geq 2$ and
$|W\cap\\{\ell_{i,1},\ell_{i,2}\\}|\geq 1$ for each $i\in[z-1]$. By relabeling
the vertices of $T$ if necessary, let
$W_{0}=(\cup_{i=1}^{z-1}\\{\ell_{i,1}\\})\cup\\{\ell_{z,1},\ell_{z,3}\\}\subseteq
W$. Then, for any distinct $i,j\in[z]$ and for any distinct
$\alpha,\beta\in[x]$, we have the following: (i)
$\textnormal{code}_{W_{0},1}(\ell_{i,2})=\textnormal{code}_{W_{0},1}(\ell_{j,2})=\textnormal{code}_{W_{0},1}(m_{\alpha})=\textnormal{code}_{W_{0},1}(m_{\beta})$,
$R_{1}\\{\ell_{i,2},\ell_{j,2}\\}=\\{\ell_{i,2},v_{i},\ell_{j,2},v_{j}\\}$,
$R_{1}\\{m_{\alpha},m_{\beta}\\}=\\{m_{\alpha},u_{\alpha},m_{\beta},u_{\beta}\\}$
(if $x\geq 2$), and
$R_{1}\\{\ell_{i,2},m_{\alpha}\\}=\\{\ell_{i,2},v_{i},m_{\alpha},u_{\alpha}\\}$
(if $x\geq 1$); (ii) for $k\geq 2$,
$\textnormal{code}_{W_{0},k}(\ell_{i,2})\neq\textnormal{code}_{W_{0},k}(\ell_{j,2})$.
If $k=1$ and $z=2$, then the first player has a winning strategy: (i) in the
$M$-game, $M^{*}$ can select $\ell_{2,3}$ and then exactly one vertex of each
pair in
$\\{\\{\ell_{1,1},\ell_{1,2}\\},\\{\ell_{2,1},\ell_{2,2}\\},\\{v_{1},v_{2}\\}\\}\cup(\cup_{i=1}^{x}\\{\\{u_{i},m_{i}\\}\\})$
thereafter, and thus occupying a distance-$1$ resolving set of $T$ in the
course of the MB$1$RG; (ii) in the $B$-game, $B^{*}$ can occupy two vertices
of $\\{\ell_{2,1},\ell_{2,2},\ell_{2,3}\\}$ after her second move, and thus
preventing $M^{*}$ from occupying vertices that form any distance-$1$
resolving set of $T$ in the course of the MB$1$RG. If $k=1$ and $z\geq 3$,
then $\dim_{1}(G)\geq
2z+x\geq\lceil\frac{1+3z+2x}{2}\rceil+1=\lceil\frac{|V(T)|}{2}\rceil+1$; thus,
$O_{R,1}(T)=\mathcal{B}$ by Observation 2.9(b). If $k\geq 2$, then
$A=(\cup_{i=1}^{z}\\{\\{\ell_{i,1},\ell_{i,2}\\}\\})\cup(\cup_{j=1}^{x}\\{\\{u_{j},m_{j}\\}\\})$
is a quasi-pairing distance-$k$ resolving set of $T$, and the first player has
a winning strategy in the MB$k$RG: (i) in the $M$-game, $M^{*}$ can occupy
$\ell_{z,3}$ after his first move and exactly one vertex of each pair in $A$
thereafter; (ii) in the $B$-game, $B^{*}$ can occupy two vertices of
$\\{\ell_{z,1},\ell_{z,2},\ell_{z,3}\\}$ after her second move.

Fourth, suppose that $M_{4}(T)=\emptyset=M_{3}(T)$. Since $T$ is not a path,
$M_{2}(T)\neq\emptyset$; notice that $|M_{2}(T)|=z\geq 2$ in this case. Let
$C=(\cup_{i=1}^{z}\\{\\{\ell_{i,1},\ell_{i,2}\\}\\})\cup(\cup_{j=1}^{x}\\{\\{u_{j},m_{j}\\}\\})$.
If $k\geq 2$, then $C$ is a pairing distance-$k$ resolving set of $T$; thus,
$O_{R,k}(T)=\mathcal{M}$ by Observation 2.12(a). So, suppose $k=1$. If $z=2$,
then $C\cup\\{\\{v_{1},v_{2}\\}\\}$ is a pairing distance-$1$ resolving set of
$T$; thus, $O_{R,1}(T)=\mathcal{M}$ by Observation 2.12(a). If $z=3$, then
$O_{R,1}(T)=\mathcal{N}$: (i) in the $B$-game of the MB$1$RG, $B^{*}$ has a
winning strategy since $\dim_{1}(T)\geq
x+5=\lceil\frac{2x+9}{2}\rceil=\lceil\frac{|V(T)|}{2}\rceil>\frac{|V(T)|}{2}$
(via an argument similar to the third case of the present proof); (ii) in the
$M$-game of the MB$1$RG, $M^{*}$ can select $v_{1}$ and then exactly one
vertex of each pair in $C\cup\\{\\{v_{2},v_{3}\\}\\}$ thereafter, and thus
occupying vertices that form a distance-$1$ resolving set of $T$. If $z\geq
4$, then $\dim_{1}(T)\geq
2z+x-1\geq\lceil\frac{3z+2x}{2}\rceil+1=\lceil\frac{|V(T)|}{2}\rceil+1$ using
a similar argument shown in the third case of the present proof; thus,
$O_{R,1}(T)=\mathcal{B}$ by Observation 2.9(b). ∎

We conclude this section with a couple of questions.

######  Question 3.10.

Among connected graphs $G$ of a fixed diameter $\lambda$, how many of the
$\lambda+1\choose 2$ ternary-valued, monotone functions on $[\lambda-1]$ are
realized as $O_{R,k}(G)$? Which ones? (We speculate that answers to the
questions are more accessible for certain classes of graphs such as trees.)

######  Question 3.11.

For a connected graph $G$ and each $k\in[\textnormal{diam}(G)-1]$, is there an
algorithm to determine the time ($M_{R,k}$, $M^{\prime}_{R,k}$, $N_{R,k}$,
$N^{\prime}_{R,k}$, $B_{R,k}$, and $B^{\prime}_{R,k}$) for the Maker or the
Breaker to win MB$k$RG?

Acknowledgements. The authors thank the anonymous referees for their helpful
comments.

## References

  * [1] A.F. Beardon and J.A. Rodríguez-Velázquez, On the $k$-metric dimension of metric spaces. Ars Math. Contemp. 16 (2019) 25-38.
  * [2] J. Beck, Combinatorial Games. Tic-Tac-Toe Theory. Cambridge University Press, Cambridge, 2008.
  * [3] Z. Beerliova, F. Eberhard, T. Erlebach, A.Hall, M. Hoffmann, M. Mihalák and L.S. Lam, Network discovery and verification. IEEE J. Sel. Areas Commun. 24 (2006) 2168-2181.
  * [4] P.S. Buczkowski, G. Chartrand, C. Poisson and P. Zhang, On $k$-dimensional graphs and their bases. Period. Math. Hungar. 46 (2003) 9-15.
  * [5] E. Duchêne, V. Gledel, A. Parreau and G. Renault, Maker-Breaker domination game. Discrete Math. 343(9) (2020) #111955.
  * [6] P. Erdös and J.L. Selfridge, On a combinatorial game. J. Combin. Theory Ser. A 14 (1973) 298-301.
  * [7] A. Estrada-Moreno, On the $(k,t)$-metric dimension of a graph. Ph.D. thesis, Universitat Rovira i Virgili, 2016.
  * [8] A. Estrada-Moreno, I.G. Yero and J.A. Rodríguez-Velázquez, On the $(k,t)$-metric dimension of graphs. Comput. J. 64 (2021) 707-720.
  * [9] H. Fernau and J.A. Rodríguez-Velázquez, On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Appl. Math. 236 (2018) 183-202.
  * [10] R.M. Frongillo, J. Geneson, M.E. Lladser, R.C. Tillquist and E. Yi, Truncated metric dimension for finite graphs. Discrete Appl. Math. 320 (2022) 150-169.
  * [11] M. Gardner, The Scientific American Book of Mathematical Puzzles and Diversions. Simon & Schuster, New York, 1959, pp. 73-83.
  * [12] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.
  * [13] J. Geneson and E. Yi, The distance-$k$ dimension of graphs. arXiv:2106.08303v2 (2021) https://arxiv.org/abs/2106.08303
  * [14] F. Harary and R.A. Melter, On the metric dimension of a graph. Ars Combin. 2 (1976) 191-195.
  * [15] D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó, Positional Games. Birkhäuser/Springer, Basel, 2014.
  * [16] C. Hernando, M. Mora, I.M. Pelayo, C. Seara and D.R. Wood, Extremal graph theory for metric dimension and diameter. Electron. J. Combin. 17 (2010) #R30.
  * [17] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs. Discrete Math. 312 (2012) 3349-3356.
  * [18] C.X. Kang, S. Klavžar, I.G. Yero and E. Yi, Maker-Breaker resolving game. Bull. Malays. Math. Sci. Soc. 44 (2021) 2081-2099.
  * [19] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs. Discrete Appl. Math. 70 (1996) 217-229.
  * [20] D.J. Klein and E. Yi, A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs. Eur. J. Pure Appl. Math. 5(3) (2012) 302-316.
  * [21] R. Nowakawski and P. Winkler, Vertex-to-vertex pursuit in a graph. Discret. Math. 43 (1983) 235-239.
  * [22] A. Sebö and E. Tannier, On metric generators of graphs. Math. Oper. Res. 29 (2004) 383-393.
  * [23] P.J. Slater, Leaves of trees. Congr. Numer. 14 (1975) 549-559.
  * [24] R.C. Tillquist, Low-dimensional embeddings for symbolic data science. Ph.D. thesis, University of Colorado, Boulder, 2020.
  * [25] R.C. Tillquist, R.M. Frongillo and M.E. Lladser, Truncated metric dimension for finite graphs. arXiv:2106.14314v1 (2021) https://arxiv.org/abs/2106.14314
  * [26] E. Yi, Fractional Maker-Breaker resolving game. Lecture Notes in Comput. Sci. 12577 (2020) 577-593.