# Maker-Breaker Strong Resolving Game

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

Let $G$ be a graph with vertex set $V$. A set $S\subseteq V$ is a _strong
resolving set_ of $G$ if, for distinct $x,y\in V$, there exists $z\in S$ such
that either $x$ lies on a $y-z$ geodesic or $y$ lies on an $x-z$ geodesic in
$G$. In this paper, we study maker-breaker strong resolving game (MBSRG)
played on a graph by two players, Maker and Breaker, where the two players
alternately select a vertex of $G$ not yet chosen. Maker wins if he is able to
choose vertices that form a strong resolving set of $G$ and Breaker wins if
she is able to prevent Maker from winning in the course of MBSRG. We denote by
$O_{\rm SR}(G)$ the outcome of MBSRG played on $G$. We obtain some general
results on MBSRG and examine the relation between $O_{\rm SR}(G)$ and $O_{\rm
R}(G)$, where $O_{\rm R}(G)$ denotes the outcome of the maker-breaker
resolving game of $G$. We determine the outcome of MBSRG played on some graph
classes, including corona product graphs and Cartesian product graphs.

Keywords: resolving set, strong resolving set, Maker-Breaker strong resolving
game, mutually maximally distant vertices, vertex cover, corona product,
Cartesian product

2010 Mathematics Subject Classification: 05C12, 05C57, 05C70, 05C76

##  1 Introduction

Erdös and Selfridge [4] 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$ and
Breaker wins otherwise. For further reading on the topic, we refer to [1, 9].
Maker-Breaker metric resolving game (MBRG) and Maker-Breaker distance-$k$
metric resolving games (MB$k$RG), respectively, played on a graph was
introduced and studied in [11] and [13]. MB$k$RG is a generalization of MBRG,
where MB$k$RG equals MBRG when $k+1$ is at least the diameter of the graph
being considered. For the fractionalization of MBRG, we refer to [22]. Other
interesting two-player games played on a graph include cop and robber game
[17] and Maker-Breaker domination game [3], for examples. In this paper, we
introduce and study Maker-Breaker strong resolving game (MBSRG) played on a
graph, where MBSRG is a variant of MBRG.

We recall the notion of a (strong) resolving set and the (strong) metric
dimension of a graph. Let $G$ be a finite, simple, undirected, and connected
graph with vertex set $V(G)$ and edge set $E(G)$. For $x,y\in V(G)$, let
$d_{G}(x,y)$ denote the minimum number of edges on a path connecting $x$ and
$y$ in $G$; we drop the subscript if it is clear in context. A set $R\subseteq
V(G)$ is a _resolving set_ of $G$ if, for distinct $x,y\in V(G)$, there exists
a vertex $z\in R$ such that $d(x,z)\neq d(y,z)$. A set $S\subseteq V(G)$ is a
_strong resolving set_ of $G$ if, for distinct $x,y\in V(G)$, there exists
$z\in S$ such that either $x$ lies on a $y-z$ geodesic or $y$ lies on an $x-z$
geodesic in $G$. The _metric dimension_ , $\dim(G)$, of $G$ is the minimum
cardinality among all resolving sets of $G$, and the _strong metric dimension_
, $\textnormal{sdim}(G)$, of $G$ is the minimum cardinality among all strong
resolving sets of $G$. For an ordered set $S=\\{u_{1},u_{2},\ldots,u_{k}\\}$
and a vertex $v\in V(G)$, the metric code of $v$ with respect to $S$, denoted
by $\textnormal{code}_{S}(v)$, is the $k$-vector
$(d(v,u_{1}),d(v,u_{2}),\ldots,d(v,u_{k}))$. Sebö and Tannier [20] observed
that, if $S$ is a strong resolving set, then the vectors
$\\{\textnormal{code}_{S}(v):v\in V(G)\\}$ uniquely determine the graph $G$
(see [14] for a proof for the claim) while providing two non-isomorphic graphs
$H_{1}$ and $H_{2}$ with $V(H_{1})=V(H_{2})$ satisfying
$\\{\textnormal{code}_{R}(v):v\in V(H_{1})\\}=\\{\textnormal{code}_{R}(v):v\in
V(H_{2})\\}$ if $R$ is a resolving set for both $H_{1}$ and $H_{2}$. Harary
and Melter [8] and Slater [21] independently introduced the concept of metric
dimension, and Sebö and Tannier [20] introduced strong metric dimension.
Applications of metric dimension include robot navigation [15], network
discovery and verification [2], sonar [21] and combinatorial optimization
[20], to name a few. It is known that determining the metric dimension and the
strong metric dimension, respectively, of a general graph is an NP-hard
problem; see [15, 6] and [18], respectively.

We recall one of the most important results regarding the strong metric
dimension of a graph. For $v\in V(G)$, the _open neighborhood_ of $v$ is
$N(v)=\\{u\in V(G):uv\in E(G)\\}$. A vertex $u\in V(G)$ is _maximally distant_
from $v\in V(G)$ if $d(u,v)\geq d(w,v)$ for every $w\in N(u)$. If $u$ is
maximally distant from $v$ and $v$ is maximally distant from $u$ in $G$, then
we say that $u$ and $v$ are _mutually maximally distant_ in $G$ and we write
$u\\!$ MMD $\\!v$. It was shown in [18] that if $x$ MMD $y$ in $G$, then
$S\cap\\{x,y\\}\neq\emptyset$ for any strong resolving set $S$ of $G$. Based
on [18] and [19], the _strong resolving graph_ of $G$, denoted by $G_{\rm
SR}$, has vertex set $V(G_{\rm SR})=\\{x\in V(G):\exists y\in V(G)\mbox{ with
}x\mbox{ MMD }y\\}$ and $uv\in E(G_{\rm SR})$ if and only if $u$ MMD $v$ in
$G$. A set $S\subseteq V(G)$ is a _vertex cover_ of $G$ if every edge of $G$
is incident with at least one vertex of $S$, and the _vertex cover number_ ,
$\alpha(G)$, of $G$ the minimum cardinality among all vertex covers of $G$. It
was shown in [18] that $\textnormal{sdim}(G)=\alpha(G_{\rm SR})$.

Now, following [11], MBRG is played on a graph $G$ by two players, Maker and
Breaker. Maker and Breaker alternately select (without missing their turn) a
vertex of $G$ not yet chosen in the course of the game. M-game (B-game,
respectively) denotes the game for which Maker (Breaker, respectively) plays
first. Maker wins MBRG if he is able to select vertices that form a resolving
set of $G$ in the course of the game; Breaker wins if Breaker can prevent
Maker from winning the game. Replacing a resolving set by a strong resolving
set, MBSRG is analogously defined in this paper. We denote by $O_{\rm R}(G)$
and $O_{\rm SR}(G)$, respectively, the outcome of MBRG and MBSRG played on
$G$.

In a network $Z$ with rivals $M$ and $B$, suppose $M$ tries to install
transmitters/sensors at some nodes in $Z$ that form a strong resolving set
(enabling $M$ to map out the entire network $Z$) while $B$ tries to prevent
$M$ from having a control over $Z$. Noting that there’s no advantage for the
second player in MBRG, it was observed in [11] that there are three realizable
outcomes for $O_{\rm R}(G)$. Analogously, there are three realizable outcomes
for $O_{\rm SR}(G)$ as follows: (i) $O_{\rm SR}(G)=\mathcal{M}$ if Maker has a
winning strategy for both the M-game and the B-game; (ii) $O_{\rm
SR}(G)=\mathcal{B}$ if Breaker has a winning strategy for both the M-game and
the B-game; (iii) $O_{\rm SR}(G)=\mathcal{N}$ if the first player has a
winning strategy. In [11, 13], the authors studied the minimum number of
moves/steps/time for Maker (Breaker, respectively) to win the game provided
Maker (Breaker, respectively) has a winning strategy in MBRG or MB$k$RG.
Analogously, one can define the minimum number of moves/steps/time for each
player to win or lose the MBSRG. However, in this paper, we will focus on the
outcomes of MBSRG played on graphs.

The paper is organized as follows. In Section 2, we obtain some general
results on the outcome of MBSRG and study the relation between $O_{\rm SR}(G)$
and $O_{\rm R}(G)$. In Section 3, we determine $O_{\rm SR}(G)$ for some graph
classes, including corona product graphs and Cartesian product graphs.

We recall some additional terminology and notations. The _diameter_ ,
$\textnormal{diam}(G)$, of $G$ is $\max\\{d(u,w):u,w\in V(G)\\}$. The _degree_
of a vertex $v\in V(G)$, denoted by $\deg_{G}(v)$, is $|N(v)|$; a _leaf_ (or
an _end-vertex_) is a vertex of degree one, a _support vertex_ is a vertex
that is adjacent to a leaf, and a _major vertex_ is a vertex of degree at
least three. For $X\subseteq V(G)$, $G[X]$ denotes the subgraph of $G$ induced
by the vertices in $X$; i.e., for $x,y\in X$, $xy\in E(G[X])$ if and only if
$xy\in E(G)$. Two distinct vertices $u$ and $w$ in a graph are called
_adjacent twins_ if $N(u)\cup\\{u\\}=N(w)\cup\\{w\\}$ and they are called
_non-adjacent twins_ if $N(u)=N(w)$; $u$ and $w$ are called _twins_ if they
are either adjacent twins or non-adjacent twins. Let $P_{n}$, $C_{n}$, and
$K_{n}$, respectively, denote the path, the cycle, and the complete graph on
$n$ vertices, and let $K_{s,t}$ denote the complete bi-partite graph with two
parts of sizes $s$ and $t$. For any positive integer $k$, let $[k]$ denote the
set $\\{1,2,\ldots,k\\}$.

##  2 General results, and $O_{\rm SR}(G)$ versus $O_{\rm R}(G)$

In this section, we obtain some general results on MBSRG and examine the
relationship between $O_{\rm SR}(G)$ and $O_{\rm R}(G)$. We recall some known
results on the strong metric dimension of graphs. A set $X\subseteq V(G)$ is
called a _twin-free clique_ if no two vertices of $X$ are twins in $G$ and
$G[X]$, the subgraph induced by $X$, forms a clique. The _twin-free clique
number_ , $\overline{\omega}(G)$, of a graph $G$ is the maximum cardinality
among all twin-free cliques in $G$.

######  Theorem 2.1.

_[18]_ For any connected graph $G$, $\textnormal{sdim}(G)=\alpha(G_{\rm SR})$.

######  Theorem 2.2.

_[23]_ Let $G$ be a connected graph of order $n\geq 2$. Then
$1\leq\textnormal{sdim}(G)\leq n-1$, and we have the following:

  * (a)

$\textnormal{sdim}(G)=1$ if and only if $G=P_{n}$,

  * (b)

$\textnormal{sdim}(G)=n-1$ if and only if $G=K_{n}$,

  * (c)

for $n\geq 4$, $\textnormal{sdim}(G)=n-2$ if and only if
$\textnormal{diam}(G)=2$ and $\overline{\omega}(G)=2$.

It is known that metric dimension is not a monotone parameter on subgraph
inclusion (see [5, 7]). We show that strong metric dimension is not a monotone
parameter with respect to subgraph inclusion, but it is monotone with respect
to strong resolving graphs. For analogous results on the fractional strong
metric dimension of graphs, we refer to [12].

######  Proposition 2.3.

  * (a)

The ratio $\frac{\textnormal{sdim}(H)}{\textnormal{sdim}(G)}$ is arbitrarily
large for suitable choice of graphs $H\subset G$.

  * (b)

If $H_{\rm SR}\subseteq G_{\rm SR}$, then
$\textnormal{sdim}(H)\leq\textnormal{sdim}(G)$.

###### Proof.

(a) We recall the following construction from [7]. For $m\geq 2$, let
$H=K_{\frac{m(m+1)}{2}}$ and let $V(H)$ be partitioned into
$V_{1},V_{2},\ldots,V_{m}$ such that $V_{i}=\cup_{j=1}^{i}\\{w_{i,j}\\}$ with
$|V_{i}|=i$ for each $i\in[m]$. Let $G$ be the graph obtained from the
disjoint union of $H$ and $m$ isolated vertices $u_{1},u_{2},\ldots,u_{m}$ by
joining edges as follows: (i) for each $i\in[m-1]$, $u_{i}$ is adjacent to
each vertex of $V_{i}\cup(\cup_{j=i+1}^{m}\\{w_{j,i}\\})$; (ii) $u_{m}$ is
adjacent to each vertex of $V_{m}$. Note that $H_{\rm
SR}=K_{\frac{m(m+1)}{2}}$; thus, $\textnormal{sdim}(H)=\alpha(H_{\rm
SR})=\frac{m(m+1)}{2}-1=\frac{m^{2}+m-2}{2}$ by Theorems 2.1 and 2.2(b). Next,
we show that $\textnormal{sdim}(G)\leq m$. It suffices to show that
$S=\cup_{i=1}^{m}\\{u_{i}\\}$ forms a strong resolving set of $G$. Let
$w_{i,s}$ and $w_{j,t}$ be distinct vertices in $H\subseteq G$. If $i\neq j$,
say $i<j$ without loss of generality, then $w_{j,t}$ lies on a $u_{j}-w_{i,s}$
geodesic in $G$. If $i=j$ and $s\neq t$, say $s<t$ by relabeling the vertices
of $G$ if necessary, then $w_{i,s}$ lies on a $u_{s}-w_{i,t}$ geodesic in $G$.
So, $S$ is a strong resolving set of $G$ with $|S|=m$; thus,
$\textnormal{sdim}(G)\leq m$. Therefore,
$\frac{\textnormal{sdim}(H)}{\textnormal{sdim}(G)}\geq\frac{m^{2}+m-2}{2m}\rightarrow\infty$
as $m\rightarrow\infty$.

(b) Let $H_{\rm SR}\subseteq G_{\rm SR}$. Let $W$ be a minimum strong
resolving set of $G$; then $W$ is a minimum vertex cover of $G_{\rm SR}$.
Since an edge in $H_{\rm SR}$ is an edge in $G_{\rm SR}$, $W\cap V(H_{\rm
SR})$ is a vertex cover of $H_{\rm SR}$. By Theorem 2.1,
$\textnormal{sdim}(H)=\alpha(H_{\rm SR})\leq\alpha(G_{\rm
SR})=\textnormal{sdim}(G)$. ∎

As stated in Section 1, two vertices $u$ and $w$ in $G$ are twins if
$N(u)-\\{w\\}=N(w)-\\{u\\}$. Hernando et al. [10] 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 following
observation is often useful in establishing a lower bound for the (strong)
metric dimension of a graph.

######  Observation 2.4.

Let $u$ and $w$ be distinct members of the same twin equivalence class of a
graph $G$.

  * (a)

_[10]_ For any resolving set $R$ of $G$, $R\cap\\{u,w\\}\neq\emptyset$.

  * (b)

_[14]_ For any strong resolving set $S$ of $G$, $S\cap\\{u,w\\}\neq\emptyset$.

We recall the following result on the outcome of MBRG. See [11, 13] for
definitions of pairing resolving set and quasi-pairing resolving set in the
metric context; their definitions in the strong metric context, which are
essentially identical, are given in the ensuing paragraph.

######  Proposition 2.5.

Let $G$ be a connected graph.

  * (a)

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

  * (b)

_[13]_ If $G$ admits a quasi-pairing resolving set, then $O_{\rm
R}(G)\in\\{\mathcal{M},\mathcal{N}\\}$.

  * (c)

_[22]_ 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_{\rm R}(G)=\mathcal{N}$.

  * (d)

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

  * (e)

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

Analogous to the concept of a pairing dominating set (see [3]) and a pairing
(distance-$k$) resolving set (see [11, 13]), we define a pairing strong
resolving set as follows. Given a set
$X=\cup_{i=1}^{\beta}\\{\\{u_{i},w_{i}\\}\\}$ such that $\cup X\subseteq
V(G_{\rm SR})$ and $|\cup X|=2\beta$, $X$ is called a _pairing strong
resolving set_ of $G$ if a set $Z\subseteq V(G_{\rm SR})$ is a strong
resolving set of $G$ whenever the condition (${\dagger}$) $|Z|=\beta$ and
$Z\cap\\{u_{i},w_{i}\\}\neq\emptyset$ for each $i\in[\beta]$ holds; in this
case, we will also call $X$ a _pairing vertex cover_ of $G_{\rm SR}$.
Analogous to the concept of a quasi-pairing distance-$k$ resolving set in
[13], we define a quasi-pairing strong resolving set as follows. Let $X$ be as
given. If there exists a vertex $v\in V(G_{\rm SR})-\cup X$ such that
$Z\cup\\{v\\}$ is a strong resolving set of $G$ whenever $Z\subseteq V(G_{\rm
SR})$ satisfies condition (${\dagger}$), then $X$ is called a _quasi-pairing
strong resolving set_ of $G$; in this case, we will also call $X$ a _quasi-
pairing vertex cover_ of $G_{\rm SR}$.

Now, we obtain some general results on the outcome of MBSRG, which will be
used in determining $O_{\rm SR}(G)$ in Section 3. Let $\mathbb{Z}^{+}$ denote
the set of positive integers. Let $\Delta(H)$ denote the maximum degree of a
graph $H$ and, for $u\in V$, let $u^{c}$ denote $V-\\{u\\}$. Next, we obtain
our main theorem on the outcome of MBSRG.

######  Theorem 2.6.

Let $G$ be a connected graph.

  * (a)

Suppose $G$ admits a pairing strong resolving set (equivalently, if $G_{\rm
SR}$ admits a pairing vertex cover), then $O_{\rm SR}(G)=\mathcal{M}$.

  * (b)

Suppose $G$ admits a quasi-pairing strong resolving set (equivalently, if
$G_{\rm SR}$ admits a quasi-pairing vertex cover), then $O_{\rm
SR}(G)\in\\{\mathcal{M},\mathcal{N}\\}$.

  * (c)

Suppose $\Delta(G_{\rm SR})\geq 2$, then $O_{\rm
SR}(G)\in\\{\mathcal{N},\mathcal{B}\\}$.

  * (d)

Suppose $\Delta(G_{\rm SR}[u^{c}])\geq 2$ for every $u\in V(G_{\rm SR})$; then
$O_{\rm SR}(G)=\mathcal{B}$.

###### Proof.

Parts (a) and (b) follow immediately from the definitions of a pairing strong
resolving set and a quasi-pairing strong resolving set, respectively. For part
(c), suppose $G_{\rm SR}$ contains a vertex $w$ of degree at least two. In the
$B$-game, Breaker can pick $w$ and one of its neighbors of $w$ as her first
two moves, thus denying Maker a vertex cover of $G_{\rm SR}$. The following is
a proof of part (d). Breaker, playing second, picks as her first move a vertex
$v$ having at least two neighbors in $G_{\rm SR}[u^{c}]$, where $u\in V(G_{\rm
SR})$ is the first move of Maker. Breaker can pick as her second move a
neighbor of $v$ in $G_{\rm SR}$ regardless of the two moves made by Maker,
thus denying Maker a vertex cover of $G_{\rm SR}$. ∎

######  Corollary 2.7.

Let $G$ be a connected graph.

  * (a)

$O_{\rm SR}(G)=\mathcal{M}$ if and only if $G_{\rm SR}=xK_{2}$ for
$x\in\mathbb{Z}^{+}$.

  * (b)

Let $H\in\\{C_{3},P_{3},P_{4},P_{5}\\}$. If $G_{\rm SR}=H\cup xK_{2}$ for
$x\in\mathbb{Z}^{+}\cup\\{0\\}$, then $O_{\rm SR}(G)=\mathcal{N}$.

  * (c)

Let $H^{*}\in\\{K_{m},C_{m},P_{m+2},xC_{3}\cup yP_{3}\\}$, where $m\geq 4$ and
$x+y\geq 2$. If $G_{\rm SR}\supseteq H^{*}$, then $O_{\rm SR}(G)=\mathcal{B}$.

###### Proof.

(a) First, let $G_{\rm SR}=xK_{2}$ for $x\in\mathbb{Z}^{+}$ with $V(G_{\rm
SR})=\\{u_{1},u_{2},\ldots,u_{2x}\\}$ and $E(G_{\rm
SR})=\cup_{i=1}^{x}\\{u_{2i-1}u_{2i}\\}$. Since
$\cup_{i=1}^{x}\\{\\{u_{2i-1},u_{2i}\\}\\}$ is a pairing vertex cover of
$G_{\rm SR}$, we have $O_{\rm SR}(G)=\mathcal{M}$ by Theorem 2.6(a). To see
the other implication, if $\Delta(G_{\rm SR})\geq 2$, then $O_{\rm
SR}(G)\in\\{\mathcal{N},\mathcal{B}\\}$ by Theorem 2.6(c). The condition
$O_{\rm SR}(G)=\mathcal{M}$ thus implies that $\Delta(G_{\rm SR})=1$.

(b) First, suppose $G_{\rm SR}=C_{3}\cup xK_{2}$ or $G_{\rm SR}=P_{3}\cup
xK_{2}$, where $x\in\mathbb{Z}^{+}\cup\\{0\\}$, with vertex set $V(G_{\rm
SR})=\\{w_{1},w_{2},w_{3}\\}\cup\\{u_{1},u_{2},\ldots,u_{2x}\\}$. Let
$E(C_{3})=\\{w_{1}w_{2},w_{2}w_{3},w_{3}w_{1}\\}$,
$E(P_{3})=\\{w_{1}w_{2},w_{2}w_{3}\\}$, and
$E(xK_{2})=\cup_{i=1}^{x}\\{u_{2i-1}u_{2i}\\}$. Notice
$X=\\{\\{w_{1},w_{3}\\}\\}\cup(\cup_{i=1}^{x}\\{\\{u_{2i-1},u_{2i}\\}\\})$ is
a quasi-pairing vertex cover of $G_{\rm SR}$ as $Z\cup\\{w_{2}\\}$ is a strong
resolving set for $G$ satisfying condition (${\dagger}$); thus, $O_{\rm
SR}(G)\in\\{\mathcal{M},\mathcal{N}\\}$ by Theorem 2.6(b). In the B-game,
Breaker can select $w_{2}$ as her first move and a neighbor of $w_{2}$ as her
second move, thus denying Maker a vertex cover. We thus have $O_{\rm
SR}(G)=\mathcal{N}$.

Second, suppose $G_{\rm SR}=P_{4}\cup xK_{2}$, where
$x\in\mathbb{Z}^{+}\cup\\{0\\}$, with vertex set $V(G_{\rm
SR})=\\{w_{1},w_{2},w_{3},w_{4}\\}\cup\\{u_{1},u_{2},\ldots,u_{2x}\\}$ and
edge set $E(G_{\rm
SR})=\\{w_{1}w_{2},w_{2}w_{3},w_{3}w_{4}\\}\cup(\cup_{i=1}^{x}\\{u_{2i-1}u_{2i}\\})$.
Notice
$X=\\{\\{w_{3},w_{4}\\}\\}\cup(\cup_{i=1}^{x}\\{\\{u_{2i-1},u_{2i}\\}\\})$ is
a quasi-pairing vertex cover of $G_{\rm SR}$ as $Z\cup\\{w_{2}\\}$ is a strong
resolving set for $G$ satisfying condition (${\dagger}$), rendering $O_{\rm
SR}(G)\in\\{\mathcal{M},\mathcal{N}\\}$ by Theorem 2.6(b). In the B-game,
Breaker can select $w_{2}$ as her first move and a neighbor of $w_{2}$ as her
second move, thus denying Maker a vertex cover. We thus have $O_{\rm
SR}(G)=\mathcal{N}$.

Third, suppose $G_{\rm SR}=P_{5}\cup xK_{2}$, where
$x\in\mathbb{Z}^{+}\cup\\{0\\}$. In the M-game, Maker picks as his first move
the central vertex $u$ of the $P_{5}$. Then (_the derived strong resolving
graph_) $G_{\rm SR}[u^{c}]=(x+2)K_{2}$, and Maker wins the B-game played on
the derived strong resolving graph by part (a) of the present corollary. In
the B-game, Breaker picks as her first move any degree-two vertex $u$ of the
$P_{5}$, and she can pick as her second move a neighbor of $u$, thus denying
Maker a vertex cover of $G_{\rm SR}$.

(c) This part, as well as other consequences, follows immediately from part
(d) of Theorem 2.6. ∎

Next, we provide a realization result on the outcome of MBSRG. We recall some
terminology and notations. Fix a tree $G$. A leaf $\ell$ is called a _terminal
vertex_ of a major vertex $v$ if $d(\ell,v)<d(\ell,w)$ for every other major
vertex $w$ in $G$. The terminal degree, $\textnormal{ter}_{G}(v)$, of a major
vertex $v$ is the number of terminal vertices of $v$ in $G$. An _exterior
major vertex_ is a major vertex that has a positive terminal degree. We denote
by $\sigma(G)$ and $ex(G)$, respectively, the number of leaves and the number
of exterior major vertices of $G$.

######  Proposition 2.8.

For each $n\geq 4$, there exist graphs $G_{1}$, $G_{2}$, $G_{3}$ of order $n$
such that $O_{\rm SR}(G_{1})=\mathcal{M}$, $O_{\rm SR}(G_{2})=\mathcal{N}$ and
$O_{\rm SR}(G_{3})=\mathcal{B}$.

###### Proof.

Let $n\geq 4$. Let $G_{1}$ be an $n$-path, $G_{2}$ be a tree with
$ex(G_{2})=1$ and $\sigma(G_{2})=3$, and $G_{3}$ be a complete graph on $n$
vertices. Then $(G_{1})_{\rm SR}=K_{2}$, $(G_{2})_{\rm SR}=K_{3}$ and
$(G_{3})_{\rm SR}=K_{n}$, where $n\geq 4$. By Corollary 2.7, we have $O_{\rm
SR}(G_{1})=\mathcal{M}$, $O_{\rm SR}(G_{2})=\mathcal{N}$ and $O_{\rm
SR}(G_{3})=\mathcal{B}$. ∎

Next, we examine the relationship between $O_{\rm SR}(G)$ and $O_{\rm R}(G)$.
We begin with the following useful observation.

######  Observation 2.9.

_[20]_ For any connected graph $G$, a strong resolving set of $G$ is a
resolving set of $G$.

To facilitate statements, let us identify
$\mathcal{B},\mathcal{N},\mathcal{M}$ with $-1,0,1$ respectively. Observation
2.9, along with the rules of MBRG and MBSRG, implies $O_{\rm SR}(G)\leq O_{\rm
R}(G)$. We thus have the following result.

######  Corollary 2.10.

The set
$\\{(\mathcal{B},\mathcal{B}),(\mathcal{B},\mathcal{N}),(\mathcal{B},\mathcal{M}),(\mathcal{N},\mathcal{N}),(\mathcal{N},\mathcal{M}),(\mathcal{M},\mathcal{M})\\}$
is a codomain of the ordered pair $(O_{\rm SR}(G),O_{\rm R}(G))$, viewed as a
function on the space of graphs.

We next show that the codomain identified in Corollary 2.10 is in fact the
range of $(O_{\rm SR}(G),O_{\rm R}(G))$.

######  Proposition 2.11.

  * (a)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{M}=O_{\rm R}(G)$.

  * (b)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{N}=O_{\rm R}(G)$.

  * (c)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{B}=O_{\rm R}(G)$.

  * (d)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{N}$ and $O_{\rm
R}(G)=\mathcal{M}$.

  * (e)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{B}$ and $O_{\rm
R}(G)=\mathcal{M}$.

  * (f)

There exist graphs $G$ satisfying $O_{\rm SR}(G)=\mathcal{B}$ and $O_{\rm
R}(G)=\mathcal{N}$.

###### Proof.

(a) Let $G$ be an $n$-path given by $u_{1},u_{2},\ldots,u_{n}$, where $n\geq
2$. Then $G_{\rm SR}=K_{2}$ and $\\{\\{u_{1},u_{n}\\}\\}$ is a pairing
(strong) resolving set of $G$. Thus, $O_{\rm SR}(G)=\mathcal{M}=O_{\rm R}(G)$
by Corollary 2.7(a) and Proposition 2.5(a).

(b) Let $G\in\\{K_{3},K_{1,3}\\}$. Then $G_{\rm SR}=C_{3}$ and $G$ has exactly
one twin equivalence class of cardinality $3$ with $\dim(G)=2$. So, $O_{\rm
SR}(G)=\mathcal{N}=O_{\rm R}(G)$ by Corollary 2.7(b) and Proposition 2.5(c).

(c) Let $G$ be the star $K_{1,x}$ on ($x+1$) vertices, where $x\geq 4$. Then
$G_{\rm SR}=K_{x}$ and the leaves of $G$ form a twin equivalence class of
cardinality $x$, where $x\geq 4$. So, $O_{\rm SR}(G)=\mathcal{B}=O_{\rm R}(G)$
by Corollary 2.7(c) and Proposition 2.5(d).

(d) Let $G$ be a tree with $ex(G)=1$ and $\sigma(G)=3$ such that
$\ell_{1},\ell_{2},\ell_{3}$ are the terminal vertices of the exterior major
vertex $v$ in $G$ with $d(v,\ell_{1})\geq 2$, $d(v,\ell_{2})\geq 2$ and
$d(v,\ell_{3})\geq 1$. For each $i\in[2]$, let $s_{i}$ be the support vertex
lying on the $v-\ell_{i}$ path. Then $G_{\rm SR}=C_{3}$ and
$\\{\\{s_{1},\ell_{1}\\},\\{s_{2},\ell_{2}\\}\\}$ is a pairing resolving set
of $G$. So, $O_{\rm SR}(G)=\mathcal{N}$ by Corollary 2.7(b) and $O_{\rm
R}(G)=\mathcal{M}$ by Proposition 2.5(a).

(e) Let $G$ be a tree with $ex(G)=1$ and $\sigma(G)=x\geq 4$. Let $v$ be the
exterior major vertex and $\ell_{1},\ell_{2},\ldots,\ell_{x}$ be the terminal
vertices of $v$ in $G$ such that $d(v,\ell_{x})\geq 1$ and $d(v,\ell_{i})\geq
2$ for each $i\in[x-1]$. For each $i\in[x-1]$, let $s_{i}$ be the support
vertex lying on the $v-\ell_{i}$ path. Since $G_{\rm SR}=K_{x}\supseteq
K_{4}$, $O_{\rm SR}(G)=\mathcal{B}$ by Corollary 2.7(c). Since
$\cup_{i=1}^{x-1}\\{\\{s_{i},\ell_{i}\\}\\}$ is a pairing resolving set of
$G$, $O_{\rm R}(G)=\mathcal{M}$ by Proposition 2.5(a).

(f) Let $G$ be a tree with $ex(G)=1$ and $\sigma(G)=x\geq 4$. Let $v$ be the
exterior major vertex and $\ell_{1},\ell_{2},\ldots,\ell_{x}$ be the terminal
vertices of $v$ in $G$ such that
$d(v,\ell_{x-2})=d(v,\ell_{x-1})=d(v,\ell_{x})=1$ and $d(v,\ell_{i})\geq 2$
for each $i\in[x-3]$. For each $i\in[x-3]$, let $s_{i}$ be the support vertex
lying on the $v-\ell_{i}$ path in $G$. Since $G_{\rm SR}=K_{x}\supseteq
K_{4}$, $O_{\rm SR}(G)=\mathcal{B}$ by Corollary 2.7(c). Next, we show that
$O_{\rm R}(G)=\mathcal{N}$. Note that, for any resolving set $W$ of $G$,
$|W\cap\\{\ell_{x-2},\ell_{x-1},\ell_{x}\\}|\geq 2$ by Observation 2.4(a). Let
$X=(\cup_{i=1}^{x-3}\\{\\{s_{i},\ell_{i}\\}\\})\cup\\{\\{\ell_{x-2},\ell_{x-1}\\}\\}$,
and let $Z\subseteq V(G)$ with $|Z|=x-2$ such that
$Z\cap\\{\ell_{x-2},\ell_{x-1}\\}\neq\emptyset$ and
$Z\cap\\{s_{i},\ell_{i}\\}\neq\emptyset$ for each $i\in[x-3]$. Since
$\\{\ell_{x}\\}\cup Z$ forms a minimum resolving set of $G$, $X$ is a quasi-
pairing resolving set of $G$. So, $O_{\rm
R}(G)\in\\{\mathcal{M},\mathcal{N}\\}$ by Proposition 2.5(b). In the B-game,
Breaker can select two vertices of $\\{\ell_{x-2},\ell_{x-1},\ell_{x}\\}$, and
thus preventing Maker from occupying vertices that form a resolving set of
$G$. Thus, $O_{\rm R}(G)=\mathcal{N}$. ∎

##  3 Some graph classes

In this section, we examine the outcome of MBSRG played on some graph classes
such as trees, cycles, the Petersen graph, complete multipartite graphs,
corona product graphs and Cartesian product graphs.

###  3.1 Trees, Cycles, Petersen Graph, Complete Multipartite Graphs

We begin with the following observation for MBSRG that is analogous to the
result obtained in [11] for MBRG. We provide its proof to be self-contained.

######  Observation 3.1.

Let $G$ be a connected graph of order $n\geq 2$.

  * (a)

If $O_{\rm SR}(G)=\mathcal{M}$, then
$\textnormal{sdim}(G)\leq\lfloor\frac{n}{2}\rfloor$.

  * (b)

If $\textnormal{sdim}(G)\geq\lceil\frac{n}{2}\rceil+1$, then $O_{\rm
SR}(G)=\mathcal{B}$.

###### Proof.

Let $G$ be a connected graph of order $n\geq 2$.

(a) Suppose $O_{\rm SR}(G)=\mathcal{M}$. In the B-game, Maker can select at
most $\lfloor\frac{n}{2}\rfloor$ vertices in the course of MBSRG. Since Maker
must occupy at least $\textnormal{sdim}(G)$ vertices, it follows that
$\textnormal{sdim}(G)\leq\lfloor\frac{n}{2}\rfloor$.

(b) Suppose $\textnormal{sdim}(G)\geq\lceil\frac{n}{2}\rceil+1$. Since Maker
can occupy at most $\lceil\frac{n}{2}\rceil$ vertices in the course of MBSRG,
Maker fails to occupy vertices that form a strong resolving set of $G$. Thus,
$O_{\rm SR}(G)=\mathcal{B}$. ∎

Next, we recall the strong metric dimension of trees, cycles, the Petersen
graph and complete multi-partite graphs.

######  Proposition 3.2.

  * (a)

_[20]_ For any tree $T$ of order at least two,
$\textnormal{sdim}(T)=\sigma(T)-1$.

  * (b)

_[20]_ For $n\geq 3$, $\textnormal{sdim}(C_{n})=\lceil\frac{n}{2}\rceil$.

  * (c)

_[24]_ For the Petersen graph $\mathcal{P}$,
$\textnormal{sdim}(\mathcal{P})=8$.

  * (d)

_[24]_ For $k\geq 2$, let $G=K_{a_{1},\ldots,a_{k}}$ be a complete $k$-partite
graph of order $n=\sum_{i=1}^{k}a_{i}\geq 3$. Let $s$ be the number of partite
sets of $G$ consisting of exactly one element. Then

$\textnormal{sdim}(G)=\left\\{\begin{array}[]{ll}n-k&\mbox{ if }s=0,\\\
n-k+s-1&\mbox{ if }s\neq 0.\end{array}\right.$

Next, we determine $O_{\rm SR}(G)$ when $G$ is a tree, a cycle, the Petersen
graph and a complete multipartite graph, respectively.

######  Proposition 3.3.

  * (a)

For any tree $T$ of order at least two,

$O_{\rm SR}(T)=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if
$\sigma(T)=2$},\\\ \mathcal{N}&\mbox{ if $\sigma(T)=3$},\\\ \mathcal{B}&\mbox{
if $\sigma(T)\geq 4$}.\end{array}\right.$

  * (b)

For $n\geq 3$,

$O_{\rm SR}(C_{n})=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if $n$ is
even},\\\ \mathcal{N}&\mbox{ if $n=3$},\\\ \mathcal{B}&\mbox{ if $n\geq 5$ and
$n$ is odd}.\end{array}\right.$

  * (c)

For the Petersen graph $\mathcal{P}$, $O_{\rm SR}(\mathcal{P})=\mathcal{B}$.

  * (d)

For $m\geq 2$, let $G=K_{a_{1},\ldots,a_{m}}$ be a complete $m$-partite graph
of order $n=\sum_{i=1}^{m}a_{i}\geq 3$. Let $s$ be the number of partite sets
of $G$ consisting of exactly one element. Then

$O_{\rm SR}(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{ if }s=a_{i}=3\mbox{ for
some }i\in[m],\\\ {}&\mbox{ if }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{ if }s\leq 2,a_{i}=3\mbox{ for exactly one
}i\in[m],\mbox{ and }a_{j}\leq 2\mbox{ for each }j\in[m]-\\{i\\},\\\
\mathcal{M}&\mbox{ if }\max\\{s,a_{i}\\}\leq 2\mbox{ for each
}i\in[m].\end{array}\right.$

###### Proof.

(a) Let $T$ be a tree of order at least two with $\sigma(T)=\sigma$; then
$T_{\rm SR}=K_{\sigma}$ with $\sigma\geq 2$. If $\sigma=2$, then $T_{\rm
SR}=K_{2}$ and $O_{\rm SR}(T)=\mathcal{M}$ by Corollary 2.7(a). If $\sigma=3$,
then $T_{\rm SR}=K_{3}$ and $O_{\rm SR}(T)=\mathcal{N}$ by Corollary 2.7(b).
If $\sigma\geq 4$, then $T_{\rm SR}=K_{\sigma}\supseteq K_{4}$; thus, $O_{\rm
SR}(T)=\mathcal{B}$ by Corollary 2.7(c).

(b) Let $n\geq 3$. First, suppose $n$ is even; then
$\textnormal{sdim}(C_{n})=\frac{n}{2}$ by Proposition 3.2(b). Since
$(C_{n})_{\rm SR}\cong\frac{n}{2}K_{2}$, we have $O_{\rm
SR}(C_{n})=\mathcal{M}$ by Corollary 2.7(a).

Second, suppose $n$ is odd; then $\textnormal{sdim}(C_{n})=\frac{n+1}{2}$ by
Proposition 3.2(b) and $(C_{n})_{\rm SR}=C_{n}$. If $n=3$, then $O_{\rm
SR}(C_{3})=\mathcal{N}$ by Corollary 2.7(b). If $n\geq 5$, then $O_{\rm
SR}(C_{n})=\mathcal{B}$ by Corollary 2.7(c).

(c) For the Petersen graph $\mathcal{P}$, we have
$\textnormal{sdim}(\mathcal{P})=8>6=\lceil\frac{|V(\mathcal{P})|}{2}\rceil+1$
by Proposition 3.2(c). By Observation 3.1(b), $O_{\rm
SR}(\mathcal{P})=\mathcal{B}$.

(d) Let $G$ be a complete $m$-partite graph described in the statement of this
proposition. First, suppose $s\geq 4$ or $a_{i}\geq 4$ for some $i\in[m]$.
Then $G_{\rm SR}\supseteq K_{4}$ and $O_{\rm SR}(G)=\mathcal{B}$ by Corollary
2.7(c).

Second, suppose $\max\\{s,a_{i}\\}=3$ for each $i\in[m]$. If $s=a_{i}=3$ for
some $i\in[m]$ or $a_{i}=a_{j}=3$ for distinct $i,j\in[m]$, then $G_{\rm
SR}\supseteq 2C_{3}$ and $O_{\rm SR}(G)=\mathcal{B}$ by Corollary 2.7(c). If
$s=3$ and $a_{i}\leq 2$ for each $i\in[m]$, then $G_{\rm
SR}=C_{3}\cup(m-3)K_{2}$ and $O_{\rm SR}(G)=\mathcal{N}$ by Corollary 2.7(b).
If $s\in\\{1,2\\}$ and $a_{i}=3$ for exactly one $i\in[m]$, then $G_{\rm
SR}=C_{3}\cup(m-2)K_{2}$ and $O_{\rm SR}(G)=\mathcal{N}$ by Corollary 2.7(b).
If $s=0$ and $a_{i}=3$ for exactly one $i\in[m]$, then $G_{\rm
SR}=C_{3}\cup(m-1)K_{2}$ and $O_{\rm SR}(G)=\mathcal{N}$ by Corollary 2.7(b).

Third, suppose $\max\\{s,a_{i}\\}\leq 2$ for each $i\in[m]$. If $s=0$, then
$G_{\rm SR}=mK_{2}$. If $s\in\\{1,2\\}$, then $G_{\rm SR}=(m-1)K_{2}$. In each
case, $O_{\rm SR}(G)=\mathcal{M}$ by Corollary 2.7(a). ∎

###  3.2 Corona Product Graphs

Let $G$ and $H$ be two graphs of order $n$ and $m$, respectively, and let
$V(G)=\\{u_{1},u_{2},\dots,u_{n}\\}$. The corona product $G\odot H$ is
obtained from $G$ and $n$ copies of $H$, say $H_{1},H_{2},\ldots,H_{n}$, by
adding an edge from $u_{i}$ to every vertex of $H_{i}$ for each $i\in[n]$. 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 joining an edge between each vertex of
$G$ and each vertex of $H$. We note that $K_{1}\odot H=K_{1}+H$. For the
strong metric dimension of corona product graphs, see [16]; for the fractional
strong metric dimension of corona product graphs, see [12]. We first consider
$O_{\rm SR}(G\odot H)$ when $G$ is a connected graph of order at least two.

######  Proposition 3.4.

Let $G$ be a connected graph of order $n\geq 2$, and let $H$ be a graph of
order $m\geq 1$.

  * (a)

If $n\geq 4$, then $O_{\rm SR}(G\odot H)=\mathcal{B}$.

  * (b)

If $n=3$, then $O_{\rm SR}(G\odot
H)=\left\\{\begin{array}[]{ll}\mathcal{N}&\mbox{ if }m=1,\\\
\mathcal{B}&\mbox{ if }m\geq 2.\end{array}\right.$

  * (c)

If $n=2$, then $O_{\rm SR}(G\odot
H)=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if }m=1,\\\
\mathcal{B}&\mbox{ if }m\geq 2.\end{array}\right.$

###### Proof.

Let $G$ be a connected graph of order $n\geq 2$ and $H$ be a graphs of order
$m\geq 1$. Let $V(G)=\\{u_{1},u_{2},\ldots,u_{n}\\}$ and let
$H_{1},\ldots,H_{n}$ be copies of $H$. For each $i\in[n]$, let
$V(H_{i})=\\{w_{i,1},\ldots,w_{i,m}\\}$, where the vertex $w_{s,x}$ in $H_{s}$
corresponds to the vertex $w_{t,x}$ in $H_{t}$ for distinct $s,t\in[n]$ and
$x\in[m]$. Since $n\geq 2$, we have $V(G)\cap V((G\odot H)_{\rm
SR})=\emptyset$.

(a) Let $n\geq 4$. For distinct $i,j\in[n]$, we have $w_{i,1}$ MMD $w_{j,1}$
in $G\odot H$. So, $(G\odot H)_{\rm SR}\supseteq K_{4}$ and $O_{\rm SR}(G\odot
H)=\mathcal{B}$ by Corollary 2.7(c).

(b) Let $n=3$. If $m=1$, then $(G\odot H)_{\rm SR}=C_{3}$ and $O_{\rm
SR}(G\odot H)=\mathcal{N}$ by Corollary 2.7(b). If $m\geq 2$, we have
$w_{i,1}$ MMD $w_{j,1}$ and $w_{i,2}$ MMD $w_{j,2}$ in $G\odot H$ for any
distinct $i,j\in[3]$; thus, $(G\odot H)_{\rm SR}\supseteq 2C_{3}$ and $O_{\rm
SR}(G\odot H)=\mathcal{B}$ by Corollary 2.7(c).

(c) Let $n=2$. If $m=1$, then $(G\odot H)_{\rm SR}=K_{2}$ and $O_{\rm
SR}(G\odot H)=\mathcal{M}$ by Corollary 2.7(a). So, suppose $m\geq 2$. Since
$\textnormal{diam}(G\odot H)=3=d_{G\odot H}(w_{i,x},w_{j,z})$ for
$\\{i,j\\}=\\{1,2\\}$ and $x,z\in[m]$, we have $(G\odot H)_{\rm SR}\supseteq
C_{4}$. By Corollary 2.7(c), $O_{\rm SR}(G\odot H)=\mathcal{B}$. ∎

Next, we consider $O_{\rm SR}(K_{1}\odot H)$ when $H$ is a disconnected graph.
We obtain the following lemma that is used in proving Proposition 3.6.

######  Lemma 3.5.

Let $G$ be a connected graph. If $G_{\rm SR}=K_{1}+(aK_{2}\cup bK_{1})$ such
that $a\geq 1$ and $b\geq 0$, or $a=0$ and $b\geq 2$, then $O_{\rm
SR}(G)=\mathcal{N}$.

###### Proof.

Let $G_{\rm SR}=K_{1}+(aK_{2}\cup bK_{1})$, where $a\geq 1$ and $b\geq 0$, or
$a=0$ and $b\geq 2$. If $G_{\rm SR}=K_{1}+K_{2}=C_{3}$ (when $a=1$ and $b=0$)
or $G_{\rm SR}=K_{1}+2K_{1}=P_{3}$ (when $a=0$ and $b=2$), then $O_{\rm
SR}(G)=\mathcal{N}$ by Corollary 2.7(b). So, suppose $G_{\rm
SR}\not\in\\{C_{3},P_{3}\\}$. Since $\Delta(G_{\rm SR})\geq 2$, $O_{\rm
SR}(G)\in\\{\mathcal{N},\mathcal{B}\\}$ by Theorem 2.6(c). To prove $O_{\rm
SR}(G)=\mathcal{N}$, we need to show that Maker wins the M-game of MBSRG. Let
$v$ be the vertex in the $K_{1}\subset G_{\rm SR}$ with $\deg(v)=2a+b$. If
$a\neq 0$, let $\\{u_{1},u_{2},\ldots,u_{2a}\\}$ be the set of degree-$2$
vertices in $G_{\rm SR}$ such that $u_{2i-1}u_{2i}\in E(G_{\rm SR})$ for each
$i\in[a]$; let $X=\cup_{i=1}^{a}\\{\\{u_{2i-1},u_{2i}\\}\\}$. We consider the
M-game. If $a=0$, then Maker can choose $v$ on his first move. If $a\neq 0$,
then Maker can select $v$ on his first move and exactly one vertex of each
pair in $X$ afterwards. In each case, Maker is able to occupy a vertex cover
of $G_{\rm SR}$, and thus Maker wins the M-game of MBSRG. ∎

######  Proposition 3.6.

Let $c(H)$ denote the number of connected components of a graph $H$ with
$c(H)\geq 2$.

  * (a)

If $c(H)\geq 4$, then $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$.

  * (b)

If $c(H)=3$, then $O_{\rm SR}(K_{1}\odot
H)=\left\\{\begin{array}[]{ll}\mathcal{N}&\mbox{ if }H=3K_{1},\\\
\mathcal{B}&\mbox{ otherwise}.\end{array}\right.$

  * (c)

If $c(H)=2$, then $O_{\rm SR}(K_{1}\odot
H)=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if }H=2K_{1},\\\
\mathcal{N}&\mbox{ if }H\in\\{K_{1}\cup K_{2},K_{1}\cup P_{3}\\}\mbox{ or
}H=K_{1}\cup H^{*}\\\ \mathcal{B}&\mbox{ otherwise},\end{array}\right.$

where $H^{*}$ is a connected graph of order $m\geq 4$ such that
$\deg_{H^{*}}(w)\in\\{m-2,m-1\\}$ for each $w\in V(H^{*})$ with at most two
vertices in $H^{*}$ having degree $m-1$.

###### Proof.

Let $H$ be a disconnected graph. For $c=c(H)\geq 2$, let
$H^{1},H^{2},\ldots,H^{c}$ be the connected components of $H$ of order
$m_{1},m_{2},\ldots,m_{c}$, respectively; let
$V(H^{i})=\\{u_{i,1},\ldots,u_{i,m_{i}}\\}$ for each $i\in[c]$. Since $H$ is
disconnected, $\textnormal{diam}(K_{1}\odot H)=2$.

(a) Let $c(H)\geq 4$. Since $u_{i,1}$ MMD $u_{j,1}$ in $K_{1}\odot H$ for any
distinct $i,j\in[c]$, we have $(K_{1}\odot H)_{\rm SR}\supseteq K_{4}$. By
Corollary 2.7(c), $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$.

(b) Let $c(H)=3$. If $m_{i}=1$ for each $i\in[3]$, then $H=3K_{1}$ and
$(K_{1}\odot H)_{\rm SR}=C_{3}$; thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$
by Corollary 2.7(b). If $m_{i}\geq 2$ for some $i\in[3]$, say $m_{3}\geq 2$
without loss of generality, then $(K_{1}\odot H)_{\rm SR}\supseteq C_{4}$
since $u_{3,1}$ MMD $u_{i,1}$ and $u_{3,2}$ MMD $u_{i,1}$ in $K_{1}\odot H$
for each $i\in[2]$; thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary
2.7(c).

(c) Let $c(H)=2$. First, suppose $m_{i}=1$ for each $i\in[2]$. Then $H=2K_{1}$
and $(K_{1}\odot H)_{\rm SR}=K_{2}$; thus, $O_{\rm SR}(K_{1}\odot
H)=\mathcal{M}$ by Corollary 2.7(a).

Second, suppose $m_{i}=1$ for exactly one $i\in[2]$; let $m_{1}=1$ and
$m_{2}\geq 2$ without loss of generality. If $\textnormal{diam}(H^{2})=1$ and
$m_{2}=2$, then $H=K_{1}\cup K_{2}$ and $(K_{1}\odot H)_{\rm SR}=C_{3}$; thus,
$O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$ by Corollary 2.7(b). If
$\textnormal{diam}(H^{2})=1$ and $m_{2}\geq 3$, then $H=K_{1}\cup K_{m_{2}}$
and $(K_{1}\odot H)_{\rm SR}=K_{m_{2}+1}\supseteq K_{4}$; thus, $O_{\rm
SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary 2.7(c).

Now, let $\textnormal{diam}(H^{2})=2$; then $m_{2}\geq 3$. If $m_{2}=3$, then
$H=K_{1}\cup P_{3}$ and $(K_{1}\odot H)_{\rm SR}=K_{1}+(K_{2}\cup K_{1})$;
thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$ by Lemma 3.5. So, suppose
$m_{2}\geq 4$. If $H^{2}$ has at least three vertices of degree $m_{2}-1$, say
$\deg_{H^{2}}(u_{2,i})=m_{2}-1$ for each $i\in[3]$, then any two distinct
vertices in $\\{u_{1,1},u_{2,1},u_{2,2},u_{2,3}\\}$ are MMD pairs in
$K_{1}\odot H$; thus, $(K_{1}\odot H)_{\rm SR}\supseteq K_{4}$ and $O_{\rm
SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary 2.7(c). If $H^{2}$ has a vertex of
degree at most $m_{2}-3$, say $\deg_{H^{2}}(u_{2,1})\leq m_{2}-3$ with
$u_{2,1}u_{2,m_{2}-1}\not\in E(H^{2})$ and $u_{2,1}u_{2,m_{2}}\not\in
E(H^{2})$, then $u_{1,1}$ MMD $u_{2,j}$ and $u_{2,1}$ MMD $u_{2,j}$ in
$K_{1}\odot H$ for each $j\in\\{m_{2}-1,m_{2}\\}$; thus, $(K_{1}\odot H)_{\rm
SR}\supseteq C_{4}$ and $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary
2.7(c). If the degree of each vertex in $H^{2}$ is either $m_{2}-2$ or
$m_{2}-1$ with at most two vertices of $H^{2}$ having degree $m_{2}-1$, then
$(K_{1}\odot H)_{\rm SR}=K_{1}+\frac{m_{2}}{2}K_{2}$ (when $m_{2}$ is even) or
$(K_{1}\odot H)_{\rm SR}=K_{1}+(\frac{m_{2}-1}{2}K_{2}\cup K_{1})$ (when
$m_{2}$ is odd); thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$ by Lemma 3.5.

If $\textnormal{diam}(H^{2})=d\geq 3$, say $w_{0},w_{1},w_{2},\ldots,w_{d}$ is
a diametral path in $H^{2}$, then $u_{1,1}$ MMD $w_{i}$ and $w_{0}$ MMD
$w_{i}$ in $K_{1}\odot H$ for each $i\in\\{d-1,d\\}$; thus, $(K_{1}\odot
H)_{\rm SR}\supseteq C_{4}$ and $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by
Corollary 2.7(c).

Third, suppose $m_{i}\geq 2$ for each $i\in[2]$. In this case, $u_{1,i}$ MMD
$u_{2,j}$ in $K_{1}\odot H$ for each $i\in[m_{1}]$ and for each $j\in[m_{2}]$.
So, $(K_{1}\odot H)_{\rm SR}\supseteq C_{4}$ and $O_{\rm SR}(K_{1}\odot
H)=\mathcal{B}$ by Corollary 2.7(c). ∎

Next, we consider $O_{\rm SR}(K_{1}\odot H)$ when $H$ is a connected graph.

######  Proposition 3.7.

Let $H$ be a connected graph of order $m\geq 3$.

  * (a)

If $\textnormal{diam}(H)=1$, then $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$.

  * (b)

If $\textnormal{diam}(H)=2$, then $O_{\rm SR}(K_{1}\odot
H)\in\\{\mathcal{M},\mathcal{N},\mathcal{B}\\}$.

  * (c)

If $\textnormal{diam}(H)=3$, then $O_{\rm SR}(K_{1}\odot
H)\in\\{\mathcal{N},\mathcal{B}\\}$.

  * (d)

If $\textnormal{diam}(H)\geq 4$, then $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$.

###### Proof.

Let $H$ be a connected graph of order $m\geq 3$.

(a) Let $\textnormal{diam}(H)=1$. Then $H=K_{m}$ and $K_{1}\odot H=K_{m+1}$,
where $m\geq 3$. So, $(K_{1}\odot H)_{\rm SR}=K_{m+1}\supseteq K_{4}$ and
$O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary 2.7(c).

(b) Let $\textnormal{diam}(H)=2$. We provide graphs $H$ with
$\textnormal{diam}(H)=2$ such that $O_{\rm SR}(K_{1}\odot H)=\mathcal{M}$,
$O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$ and $O_{\rm SR}(K_{1}\odot
H)=\mathcal{B}$, respectively. If $H\in\\{P_{3},C_{4}\\}$, then
$\textnormal{diam}(H)=2$ and $O_{\rm SR}(K_{1}\odot H)=\mathcal{M}$ (see
Corollaries 3.8 and 3.9). If $H\in\\{K_{2,3},K_{1,2,3}\\}$, then
$\textnormal{diam}(H)=2$, $K_{1}\odot K_{2,3}=K_{1,2,3}$ and $K_{1}\odot
K_{1,2,3}=K_{1,1,2,3}$; thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{N}$ by
Proposition 3.3(d). If $H=K_{a,b}$ with $\min\\{a,b\\}\geq 3$, then
$\textnormal{diam}(H)=2$ and $K_{1}\odot K_{a,b}=K_{1,a,b}$, where $a,b\geq
3$; thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by Proposition 3.3(d).

(c) Let $\textnormal{diam}(H)=3$. Let $w_{0},w_{1},w_{2},w_{3}$ be a diametral
path in $H$. Since $w_{0}$ MMD $w_{2}$ and $w_{0}$ MMD $w_{3}$ in $K_{1}\odot
H$, we have $\Delta((K_{1}\odot H)_{\rm SR})\geq 2$; thus, $O_{\rm
SR}(K_{1}\odot H)\in\\{\mathcal{N},\mathcal{B}\\}$ by Theorem 2.6(c).

Next, we provide graphs $H$ with $\textnormal{diam}(H)=3$ such that $O_{\rm
SR}(K_{1}\odot H)=\mathcal{N}$ and $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$,
respectively. If $H=P_{4}$, then $\textnormal{diam}(H)=3$ and $O_{\rm
SR}(K_{1}\odot H)=\mathcal{N}$ (see Corollary 3.8). If
$H\in\\{C_{6},C_{7}\\}$, then $\textnormal{diam}(H)=3$ and $O_{\rm
SR}(K_{1}\odot H)=\mathcal{B}$ (see Corollary 3.9).

(d) Suppose $\textnormal{diam}(H)\geq 4$; let $w_{0},w_{1},\ldots,w_{d}$ be a
diametral path in $H$. Since $w_{0}$ MMD $w_{j}$ and $w_{1}$ MMD $w_{j}$ in
$K_{1}\odot H$ for each $j\in\\{d-1,d\\}$, we have $(K_{1}\odot H)_{\rm
SR}\supseteq C_{4}$; thus, $O_{\rm SR}(K_{1}\odot H)=\mathcal{B}$ by Corollary
2.7(c). ∎

Next, we determine the outcome of MBSRG played on fan graphs and wheel graphs,
where we apply Proposition 3.7 in obtaining Corollary 3.8.

######  Corollary 3.8.

For $n\geq 1$, $O_{\rm SR}(K_{1}\odot P_{n})=O_{\rm
SR}(K_{1}+P_{n})=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if
}n\in\\{1,3\\},\\\ \mathcal{N}&\mbox{ if }n\in\\{2,4\\},\\\ \mathcal{B}&\mbox{
if }n\geq 5.\end{array}\right.$

###### Proof.

First, let $n\in\\{1,2,3,4\\}$. Since $(K_{1}\odot P_{1})_{\rm SR}=K_{2}$ and
$(K_{1}\odot P_{3})_{\rm SR}=2K_{2}$, we have $O_{\rm SR}(K_{1}\odot
P_{1})=O_{\rm SR}(K_{1}\odot P_{3})=\mathcal{M}$ by Corollary 2.7(a). Since
$(K_{1}\odot P_{2})_{\rm SR}=C_{3}$ and $(K_{1}\odot P_{4})_{\rm SR}=P_{4}$,
we have $O_{\rm SR}(K_{1}\odot P_{2})=O_{\rm SR}(K_{1}\odot
P_{4})=\mathcal{N}$ by Corollary 2.7(b). Next, let $n\geq 5$; then
$\textnormal{diam}(P_{n})\geq 4$. By Proposition 3.7, $O_{\rm SR}(K_{1}\odot
P_{n})=\mathcal{B}$ for $n\geq 5$. ∎

######  Corollary 3.9.

For $n\geq 3$, $O_{\rm SR}(K_{1}\odot C_{n})=O_{\rm
SR}(K_{1}+C_{n})=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if }n=4,\\\
\mathcal{B}&\mbox{ otherwise}.\end{array}\right.$

###### Proof.

First, let $n\in\\{3,4,5\\}$. Since $K_{1}\odot C_{3}=K_{4}$, we have
$(K_{1}\odot C_{3})_{\rm SR}=K_{4}$ and $O_{\rm SR}(K_{1}\odot
C_{3})=\mathcal{B}$ by Corollary 2.7(c). Since $(K_{1}\odot C_{4})_{\rm
SR}=2K_{2}$, we have $O_{\rm SR}(K_{1}\odot C_{4})=\mathcal{M}$ by Corollary
2.7(a). Since $(K_{1}\odot C_{5})_{\rm SR}=C_{5}$, we have $O_{\rm
SR}(K_{1}\odot C_{5})=\mathcal{B}$ by Corollary 2.7(c).

Second, let $n\geq 6$; notice that $\textnormal{diam}(K_{1}\odot C_{n})=2$.
Suppose the $n$-cycle of $K_{1}\odot C_{n}$ be given by
$u_{1},u_{2},\ldots,u_{n},u_{1}$. Since any pair of distinct vertices in
$\\{u_{1},u_{3},u_{5}\\}$ and $\\{u_{2},u_{4},u_{6}\\}$, respectively, are MMD
pairs in $K_{1}\odot C_{n}$, we have $(K_{1}\odot C_{n})_{\rm SR}\supseteq
2C_{3}$. By Corollary 2.7(c), $O_{\rm SR}(K_{1}\odot C_{n})=\mathcal{B}$ for
$n\geq 6$. ∎

###  3.3 Cartesian Product Graphs

The _Cartesian product_ of two graphs $G$ and $H$, denoted by $G\square H$, is
the graph with the vertex set $V(G)\times V(H)$ such that $(u,w)$ is adjacent
to $(u^{\prime},w^{\prime})$ if and only if either $u=u^{\prime}$ and
$ww^{\prime}\in E(H)$, or $w=w^{\prime}$ and $uu^{\prime}\in E(G)$. The
_direct product_ (also known as the _tensor product_) of two graphs $G$ and
$H$, denoted by $G\times H$, is the graph with the vertex set $V(G)\times
V(H)$ such that $(u,w)$ is adjacent to $(u^{\prime},w^{\prime})$ if and only
if $uu^{\prime}\in E(G)$ and $ww^{\prime}\in E(H)$. For the strong metric
dimension of Cartesian product graphs, see [19]; for the fractional strong
metric dimension of Cartesian product graphs, see [12]. We first recall the
following result connecting Cartesian product and direct product.

######  Theorem 3.10.

_[19]_ If $G$ and $H$ are two connected graphs of order at least two, then
$(G\square H)_{\rm SR}=G_{\rm SR}\times H_{\rm SR}$.

Next, for connected graphs $G$ and $H$ of order at least two, we show that
$O_{\rm SR}(G\square H)\in\\{\mathcal{M},\mathcal{B}\\}$ and we characterize
Cartesian product graphs satisfying $O_{\rm SR}(G\square H)=\mathcal{M}$. We
begin with the following lemma that is used in proving our main result on the
outcome of MBSRG played on Cartesian product graphs.

######  Lemma 3.11.

Let $G$ and $H$ be two connected graphs of order at least two. If
$\Delta(G_{\rm SR})\geq 2$ or $\Delta(H_{\rm SR})\geq 2$, then $O_{\rm
SR}(G\square H)=\mathcal{B}$.

###### Proof.

Without loss of generality, suppose $\Delta(G_{\rm SR})\geq 2$. By Theorem
3.10, $(G\square H)_{\rm SR}=G_{\rm SR}\times H_{\rm SR}\supseteq P_{3}\times
K_{2}\supseteq 2P_{3}$. Thus, $O_{\rm SR}(G\square H)=\mathcal{B}$ by
Corollary 2.7(c). ∎

######  Theorem 3.12.

Let $G$ and $H$ be two connected graphs of order at least two. Then $O_{\rm
SR}(G\square H)\in\\{\mathcal{M},\mathcal{B}\\}$. Moreover, $O_{\rm
SR}(G\square H)=\mathcal{M}$ if and only if $G_{\rm SR}=aK_{2}$ and $H_{\rm
SR}=bK_{2}$, where $a\in\mathbb{Z}^{+}$ and $b\in\mathbb{Z}^{+}$.

###### Proof.

First, suppose $\Delta(G_{\rm SR})\geq 2$ or $\Delta(H_{\rm SR})\geq 2$. Then
$O_{\rm SR}(G\square H)=\mathcal{B}$ by Lemma 3.11.

Second, suppose $\Delta(G_{\rm SR})=1=\Delta(H_{\rm SR})$; then $G_{\rm
SR}=aK_{2}$ and $H_{\rm SR}=bK_{2}$, where $a,b\in\mathbb{Z}^{+}$. In this
case, $(G\square H)_{\rm SR}=G_{\rm SR}\times H_{\rm SR}=aK_{2}\times
bK_{2}=(2ab)K_{2}$, and thus $O_{\rm SR}(G\square H)=\mathcal{M}$ by Corollary
2.7(a). ∎

We note that $(K_{n})_{\rm SR}=K_{n}$ for $n\geq 2$, $(C_{2m-1})_{\rm
SR}=C_{2m-1}$ and $(C_{2m})_{\rm SR}=mK_{2}$ for $m\geq 2$, and $(T_{\rm
SR})=K_{\sigma}$ for any tree $T$ with $\sigma$ leaves. So, Lemma 3.11 and
Theorem 3.12 imply the following.

######  Corollary 3.13.

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

  * (a)

For $n\geq 3$, $O_{\rm SR}(G\square K_{n})=\mathcal{B}$.

  * (b)

For $n\geq 3$, $O_{\rm SR}(G\square
C_{n})=\left\\{\begin{array}[]{ll}\mathcal{M}&\mbox{ if $n$ is even and
$\Delta(G_{\rm SR})=1$},\\\ \mathcal{B}&\mbox{ if $n$ is odd or $\Delta(G_{\rm
SR})\geq 2$}.\end{array}\right.$

  * (c)

For any tree $T$ that is not a path, $O_{\rm SR}(G\square T)=\mathcal{B}$.

## References

  * [1] J. Beck, Combinatorial Games. Tic-Tac-Toe Theory. Cambridge University Press, Cambridge, 2008.
  * [2] 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.
  * [3] E. Duchêne, V. Gledel, A. Parreau and G. Renault, Maker-Breaker domination game. Discrete Math. 343(9) (2020) #111955.
  * [4] P. Erdös and J.L. Selfridge, On a combinatorial game. J. Combin. Theory Ser. A 14 (1973) 298-301.
  * [5] L. Eroh, C.X. Kang and E. Yi, Metric dimension and zero forcing number of two families of line graphs. Math. Bohem. 139(3) (2014) 467-483.
  * [6] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York, 1979.
  * [7] J. Geneson and E. Yi, Broadcast dimension of graphs. Australas. J. Combin. 83(2) (2022) 243-264.
  * [8] F. Harary and R.A. Melter, On the metric dimension of a graph. Ars Combin. 2 (1976) 191-195.
  * [9] D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó, Positional Games. Birkhäuser/Springer, Basel, 2014.
  * [10] 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.
  * [11] 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.
  * [12] C.X. Kang, I.G. Yero and E. Yi, The fractional strong metric dimension in three graph products. Discrete Appl. Math. 251 (2018) 190-203.
  * [13] C.X. Kang and E. Yi, Maker-Breaker metric resolving games on graphs. Discrete Math. Algorithms Appl. (2023) https://doi.org/10.1142/S1793830923500064
  * [14] C.X. Kang and E. Yi, The fractional strong metric dimension of graphs. Lecture Notes in Comput. Sci. 8287 (2013) 84-95.
  * [15] S. Khuller, B. Raghavachari and A. Rosenfeld, Landmarks in graphs. Discrete Appl. Math. 70 (1996) 217-229.
  * [16] D. Kuziak, I.G. Yero, J.A. Rodríguez-Velázquez, On the strong metric dimension of corona product graphs and join graphs. Discrete Appl. Math. 161 (2013) 1022-1027.
  * [17] R. Nowakawski and P. Winkler, Vertex-to-vertex pursuit in a graph. Discret. Math. 43 (1983) 235-239.
  * [18] O.R. Oellermann, J. Peters-Fransen, The strong metric dimension of graphs and digraphs. _Discrete Appl. Math._ 155 (2007) 356-364.
  * [19] J.A. Rodríguez-Velázquez, I.G. Yero, D. Kuziak, O.R. Oellermann, On the strong metric dimension of Cartesian and direct products of graphs. Discrete Appl. Math. 335 (2014) 8-19.
  * [20] A. Sebö and E. Tannier, On metric generators of graphs. Math. Oper. Res. 29 (2004) 383-393.
  * [21] P.J. Slater, Leaves of trees. Congr. Numer. 14 (1975) 549-559.
  * [22] E. Yi, Fractional Maker-Breaker resolving game. Lecture Notes in Comput. Sci. 12577 (2020) 577-593.
  * [23] E. Yi, On strong metric dimension of graphs and their complements. Acta Math. Sin. (Engl. Ser.) 29(8) (2013) 1479-1492.
  * [24] E. Yi, On the strong metric dimension of permutation graphs. J. Combin. Math. Combin. Comput. 90 (2014) 39-58.