Maker–Breaker Resolving Game Played on Lexicographic Products of Graphs

Abstract 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:mi>H</mml:mi> </mml:mrow> </mml:math> . 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 }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> and in $$G\circ C_{2\ell }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>ℓ</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> , Resolver always wins, while in $$G\circ P_{2\ell +1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> and in $$G\circ C_{2\ell +1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>C</mml:mi> <mml:mrow> <mml:mn>2</mml:mn> <mml:mi>ℓ</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> </mml:math> the same conclusion holds provided G is free from false twins. On the other hand, Spoiler always wins on $$G\circ P_5$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>G</mml:mi> <mml:mo>∘</mml:mo> <mml:msub> <mml:mi>P</mml:mi> <mml:mn>5</mml:mn> </mml:msub> </mml:mrow> </mml:math> . In most of the cases, the corresponding Maker-Breaker resolving number is also determined.