Maker-Breaker resolving game played on lexicographic products of graphs

Savitha K S, Sandi Klavžar, Tijo James · 2025

Read Maker-Breaker resolving game played on lexicographic products of graphs by Savitha K S, Sandi Klavžar, Tijo James (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-00813.txt.

Introduction

Savitha K S, Sandi Klavžar, and Tijo James study a two-player graph game in a 2025 paper. In the Maker-Breaker resolving game, two players take turns claiming unplayed vertices of a graph. One player, Resolver, wants to claim every vertex of some resolving set. A resolving set pins down all vertices by their distances to it.

The other player, Spoiler, wants to grab at least one vertex from every resolving set, blocking Resolver. The authors study the game on lexicographic products, a way of building big graphs from smaller ones. Knowing who wins helps judge how robust location schemes on networks can be.

Catalog record

CREATORSavitha K S, Sandi Klavžar, Tijo James
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-00813

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Maker-Breaker resolving game played on lexicographic products of graphs Savitha K S, Sandi Klavžar, Tijo James Abstract In the Maker-Breaker resolving game, two players named Resolver and Spoiler alternately select unplayed vertices of a given graph G G . The aim of Resolver is to select all the vertices of some resolving set of G G , while Spoiler aims to select at least one vertex from every resolving set of G G . In this paper, this game is investigated on the lexicographic product of graphs. It is proved that if Spoiler has a winning strategy on a graph H H no matter who starts the game, or if the first player has a winning strategy on H H , then Spoiler always has a winning strategy on G ∘ H G\circ H . Special attention is paid to lexicographic products in which the second factor is either complete, or a path, or a cycle. For instance, in G ∘ P 2 ​ ℓ G\circ P_{2\ell} and in G ∘ C 2 ​ ℓ G\circ C_{2\ell} , Resolver always wins, while in G ∘ P 2 ​ ℓ + 1 G\circ P_{2\ell+1} and in G ∘ C 2 ​ ℓ + 1 G\circ C_{2\ell+1} the same conclusion holds provided G G is free from false twins. On the other hand, Spoiler always wins on G ∘ P 5 G\circ P_{5} . In most of the cases, the corresponding Maker-Breaker resolving number is also determined. a Department of Mathematics, St. Paul’s College, Kalamassery, India b Faculty of Mathematics and Physics, University of Ljubljana, Slovenia c Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia d Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia e Department of Mathematics, Pavanatma College, Murickassery, India Keywords: Maker-Breaker game; metric dimension; resolving set; Maker-Breaker resolving game; lexicographic product of graphs AMS Subj. Class. (2020) : 05C12, 05C57, 05C76 1 Introduction Let G=(V(G),E(G)) be a simple, finite, connected graph with at least two vertices. A set W\subseteq V(G) is a resolving set of G , if for every pair of distinct vertices x and y of G , there exists a vertex z\in W such that d(x,z)\neq d(y,z) , where d(u,v) denotes the shortest-path distance between the vertices u and v . Among all resolving sets of G , one with minimum cardinality is a metric basis and its cardinality is defined to be the metric dimension of G , denoted by \dim(G) . As an entry point into this field of research, we recommend the review article [ 20 ] and recent papers [ 4 , 13 , 19 ] . The Maker-Breaker resolving game was introduced in [ 10 ] and the authors investigated the same in the corona product of graphs [ 7 ] . A closely related Maker-Breaker strong resolving game has been investigated in [ 12 ] , the fractional version of the game in [ 21 ] , while for the general framework on Maker-Breaker games see Chapter 2 of the book [ 6 ] . For more on these games, see also the recent articles [ 2 , 5 ] and the references therein. In the Maker-Breaker resolving game ( MBRG for short), two players, named Resolver and Spoiler, alternately select unplayed vertices of a given graph G . The aim of Resolver is to select all the vertices of some resolving set of G , while Spoiler aims to select at least one vertex from every resolving set of G . The player who achieves their goal is the winner of the game. If Resolver starts the game, we speak of an R-game , otherwise we speak of an S-game . For the outcome o(G) of the MBRG played on G we have o(G)\in\{\mathcal{R},\mathcal{S},\mathcal{N}\} , with the following meaning [ 10 ] : • o(G)=\mathcal{R} : Resolver has a winning strategy no matter who starts the game; • o(G)=\mathcal{S} : Spoiler has a winning strategy no matter who starts the game; • o(G)=\mathcal{N} : the first player has a winning strategy. In addition to knowing who wins the game, it is also of interest how fast the winner can achieve this. The Maker-Breaker resolving number , R_{\rm MB}(G) , is the minimum number of moves of Resolver to win the R-game in G when both players play optimally. The Maker-Breaker spoiling number , S_{\rm MB}(G) , is the minimum number of moves of Spoiler to win the R game in G when both players play optimally. For the S-game, the corresponding invariants are denoted by R_{\rm MB}^{\prime}(G) and S_{\rm MB}^{\prime}(G) . The lexicographic product G\circ H of graphs G and H has the vertex set V(G\circ H)=\{(g,h):\ g\in V(G),h\in V(H)\} and the edge set E(G\circ H)=\{(g,h)(g^{\prime},h^{\prime}):\ gg^{\prime}\in E(G),~\text{or}~g=g^{\prime}~\text{and}~hh^{\prime}\in E(H)\} . Studies on lexicographic products in various domains highlight its versatility, which offers valuable insights into network structures, information flow, and resilience. In [ 8 ] , the metric dimension of the lexicographic products is determined in terms of a parameter called the adjacency dimension. The general bounds for the metric dimension of the lexicographic product of graphs can be seen in [ 18 ] . For some other studies of the lexicographic product of graphs we refer to [ 1 , 3 , 9 , 14 , 16 , 17 ] . In this paper, we investigate the MBRG played on the lexicographic product of graphs. The following section is preparatory and, among other things, recalls known results that we need here. In Section 3, we discuss some general properties of the MBRG on lexicographic products. In particular, if G and H are nontrivial connected graphs and o(H)\in\{{\cal N},{\cal S}\} , then we show that o(G\circ H)=\mathcal{S} . In Section 4 we consider lexicographic products in which one factor is complete. We prove that if G has true twins, then S_{\rm MB}(G\circ K_{2})=S_{\rm MB}^{\prime}(G\circ K_{2})=2 , otherwise R_{\rm MB}(G\circ K_{2})=R_{\rm MB}^{\prime}(G\circ K_{2})=n(G) . In Section 5 we focus on the MBRG where the second factor is a path or a cycle, while in the concluding section we pose some open problems. 2 Preliminaries In this section, we collect known results and concepts which will be used in the rest of the paper, and add some additional definitions. Let’s start with the latter. For a positive integer \ell , we will denote the set \{1,\ldots,\ell\} by [\ell] . By n(G) we denote the order of G . For a vertex v\in V(G) , its open neighborhood is N_{G}(v)=\{u\in V(G):\ uv\in E(G)\} . Vertices u and v are twins if N(u)\setminus\{v\}=N(v)\setminus\{u\} . The twin relation is an equivalence relation, and an equivalence class under this equivalence relation is called a twin equivalence class . A pair of adjacent vertices in a twin equivalence class is termed as true twins , and a pair of non-adjacent vertices in a twin equivalence class is termed as false twins . A set S\subseteq V(G) is a dominating set of a graph G , if every vertex u\in V(G)\setminus S has a neighbor in S . A vertex x\in V(G) is a dominating vertex of G if x is adjacent to all the other vertices of G . Note that in this case

Read the complete text