Maker-breaker resolving game

DOI10.1007/S40840-020-01044-0MaRDI QIDQ2045245zbMATH OpenOpenAlexFDO

Authors Cong X. Kang, Sandi Klavžar, Eunjeong Yi, Ismael G. Yero

Publication date 12 August 2021

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.13242

zbMATH Keywords

maker-breaker gamemaker-breaker resolving gamemetric dimensionpairing resolving setresolving settwin equivalence class

Mathematics Subject Classification ID

Distance in graphs (05C12) Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: A set of vertices $W$ of a graph $G$ is a resolving set if every vertex of $G$ is uniquely determined by its vector of distances to $W$. In this paper, the Maker-Breaker resolving game is introduced. The game is played on a graph $G$ by Resolver and Spoiler who alternately select a vertex of $G$ not yet chosen. Resolver wins if at some point the vertices chosen by him form a resolving set of $G$, whereas Spoiler wins if the Resolver cannot form a resolving set of $G$. The outcome of the game is denoted by $o(G)$ and $R_{mMB}(G)$ (resp. $S_{mMB}(G)$) denotes the minimum number of moves of Resolver (resp. Spoiler) to win when Resolver has the first move. The corresponding invariants for the game when Spoiler has the first move are denoted by $R{\text{'}}_{mMB}(G)$ and $S{\text{'}}_{mMB}(G)$. Invariants $R_{mMB}(G)$, $R{\text{'}}_{mMB}(G)$, $S_{mMB}(G)$, and $S{\text{'}}_{mMB}(G)$ are compared among themselves and with the metric dimension $mdim(G)$. A large class of graphs $G$ is constructed for which $R_{mMB}(G)>mdim(G)$ holds. The effect of twin equivalence classes and pairing resolving sets on the Maker-Breaker resolving game is described. As an application $o(G)$, as well as $R_{mMB}(G)$ and $R{\text{'}}_{mMB}(G)$ (or $S_{mMB}(G)$ and $S{\text{'}}_{mMB}(G)$), are determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.

Recommendations

• Maker-breaker domination number
• The metric dimension and metric independence of a graph
• Maker-Breaker domination game
• The metric dimension for resolving several objects
• On the metric dimension of infinite graphs

Cites work

• Base size, metric dimension and other invariants of groups and graphs
• Combinatorial Games
• Domination game and an imagination strategy
• Extremal graph theory for metric dimension and diameter
• Families of regular graphs with constant metric dimension
• Fast strategies in biased Maker-Breaker games
• Handbook of product graphs
• scientific article; zbMATH DE number 5776159 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2068163 (Why is no real title available?)
• scientific article; zbMATH DE number 1749658 (Why is no real title available?)
• scientific article; zbMATH DE number 7390801 (Why is no real title available?)
• scientific article; zbMATH DE number 227006 (Why is no real title available?)
• Landmarks in graphs
• Maker-Breaker domination game
• Maker-breaker domination number
• Maker-breaker total domination game
• Metric dimension of fullerene graphs
• On a combinatorial game
• On the metric dimension of Cartesian powers of a graph
• On the Metric Dimension of Cartesian Products of Graphs
• On the WalkerMaker-WalkerBreaker games
• Positional games
• Resolvability in graphs and the metric dimension of a graph
• The connected metric dimension at a vertex of a graph
• The Maker-Breaker Rado game on a random set of integers
• The metric dimension of the lexicographic product of graphs
• The metric dimension of the lexicographic product of graphs
• The metric dimensions of a complete \(n\)-partite graph and its Cartesian product with a path

Cited in

(7)

• Hitting time results for maker-breaker games
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Fast winning strategies for staller in the maker-breaker domination game
• Maker-Breaker Metric Resolving Games on Graphs
• Maker-breaker domination game on trees when Staller wins
• Maker-breaker resolving game played on corona products of graphs
• Maker-breaker resolving game played on lexicographic products of graphs

This page was built for publication: Maker-breaker resolving game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045245)