Maker-Breaker metric resolving games on graphs.

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 ∈ V : d k (x , z) ≠ d k (y , z) }. A set S ⊆ V is a distance-k resolving set of G if S ∩ R k { x , y } ≠ ∅ for distinct x , y ∈ 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 ℳ , ℬ and , 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 = ℬ , 0 = , 1 = ℳ }. 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 { (ℬ ,) , (ℬ , ℳ) , (, ℳ) } ; we provide graphs G such that O R , 1 (G) = ℬ , O R , 2 (G) = and O R , k (G) = ℳ for k ≥ 3. Moreover, we obtain some general results on MB k RG and study the MB k RG played on some graph classes. [ABSTRACT FROM AUTHOR]