Maker-Breaker Strong Resolving Game

Abstract

Let $G$ be a graph with vertex set $V$. A set $S\subseteq V$ is a \emph{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_{\mathrm{SR}}(G)$ the outcome of MBSRG played on $G$. We obtain some general results on MBSRG and examine the relation between $O_{\mathrm{SR}}(G)$ and $O_{\mathrm{R}}(G)$, where $O_{\mathrm{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, Cartesian product graphs, and modular product graphs.

15 pages, 0 figures