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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$G\circ H$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <mi>H</mi> </mrow> </math></EquationSource> </InlineEquation>. Special attention is paid to lexicographic products in which the second factor is a complete graph, a path, or a cycle. For instance, in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$G\circ P_{2\ell }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msub> <mi>P</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> and in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$G\circ C_{2\ell }$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>, Resolver always wins, while in <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$G\circ P_{2\ell +1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msub> <mi>P</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> and in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$G\circ C_{2\ell +1}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msub> <mi>C</mi> <mrow> <mn>2</mn> <mi>ℓ</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> the same conclusion holds provided G is free from false twins. On the other hand, Spoiler always wins on <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$G\circ P_5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>∘</mo> <msub> <mi>P</mi> <mn>5</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. In most of the cases, the corresponding Maker-Breaker resolving number is also determined.

Maker–Breaker Resolving Game Played on Lexicographic Products of Graphs

期刊论文
出版模式：

开放获取
发表日期：

2026年3月19日

查看全文

Kurumbail Madom Subramanian Savitha,
Sandi Klavžar,
Tijo James

摘要

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$ $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 }$ $G \circ P_{2 ℓ}$ and in $G\circ C_{2\ell }$ $G \circ C_{2 ℓ}$ , Resolver always wins, while in $G\circ P_{2\ell +1}$ $G \circ P_{2 ℓ + 1}$ and in $G\circ C_{2\ell +1}$ $G \circ C_{2 ℓ + 1}$ the same conclusion holds provided G is free from false twins. On the other hand, Spoiler always wins on $G\circ P_5$ $G \circ P_{5}$ . In most of the cases, the corresponding Maker-Breaker resolving number is also determined.