Maker-Breaker resolving game played on lexicographic products of graphs

Savitha, K. S. (author), Klavžar, Sandi (author), James, Tijo (author)

In the Maker-Breaker resolving game, 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$. 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$ no matter who starts the game, or if the first player has a winning strategy on $H$, then Spoiler always has a winning strategy on $G\circ H$. Special attention is paid to lexicographic products in which the second factor is a complete graph, a path, or a cycle. For instance, in $G\circ P_{2\ell}$ and in $G\circ C_{2\ell}$, Resolver always wins, while in $G\circ P_{2\ell+1}$ and in $G\circ C_{2\ell+1}$ the same conclusion holds provided $G$ is free from false twins. On the other hand, Spoiler always wins on $G\circ P_5$. In most of the cases, the corresponding Maker-Breaker resolving number is also determined.

• Language: English
• Keywords: Maker-Breaker game, metric dimension, resolving set, Maker-Breaker resolving game, lexicographic product of graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.04.2026
• Year: 2026
• Number of pages: 12 str.
• Numbering: Vol. 52, iss. 2, article no. 21
• PID: 20.500.12556/RUL-181037
• UDC: 519.17
• ISSN on article: 1018-6301
• DOI: 10.1007/s41980-026-01046-x
• COBISS.SI-ID: 272611587
• Publication date in RUL: 23.03.2026

Record is a part of a journal

• Title: Bulletin of the Iranian Mathematical Society
• Shortened title: Bull. iran. math. soc.
• Publisher: Iranian Mathematical Society, Springer
• ISSN: 1018-6301
• COBISS.SI-ID: 518040345

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: igra izdelovalec-lomilec, metrična dimenzija, solventna množica, solventna igra izdelovalec-lomilec, leksikografski produkt grafov