论文标题
制造商破坏者解决游戏
Maker-Breaker resolving game
论文作者
论文摘要
如果每个顶点$ g $由$ g $的每个顶点取决于其距离为$ w $的唯一决定,则一组顶点$ w $是一个解决方案。在本文中,引入了制造商打破器的解决游戏。该游戏是在Resolver and Spoiter的图表$ G $上播放的,他们交替选择尚未选择的$ G $的顶点。如果他在某个时候,他选择的顶点会赢得$ g $的胜利,而如果解析器无法形成$ g $的解决方案,则扰流板会获胜。游戏的结果用$ o(g)$和$ r _ {\ rm mb}(g)$表示(分别$ s _ {\ rm mb}(g)$)表示分辨率(reves。peiper)在分辨率第一步时赢得胜利的最小移动次数。当扰流板具有第一步时,游戏的相应不变性用$ r'_ {\ rm mb}(g)$和$ s'_ {\ rm mb}(g)$表示。不变性$ r _ {\ rm mb}(g)$,$ r'_ {\ rm mb}(g)$,$ s _ {\ rm mb}(g)$,和$ s'_ {\ rm mb}(g)$与自身中的比较,并与Metress Dipension Dipension $ pym比较。构建了一大批图形$ g $,为此$ r _ {\ rm mb}(g)> {\ rm dim}(g)$ holds。描述了双等效类别和配对解决集对制造商破坏者解决游戏的效果。作为应用程序$ o(g)$,以及$ r _ {\ rm mb}(g)$和$ r'_ {\ rm mb}(g)$(或$ s _ {\ rm mb}(g)$和$ s'_ _ _ _ _ {\ rm mb}(g)$的图表,包括绘图库,包括绘制图。圆环网格图。
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_{\rm MB}(G)$ (resp. $S_{\rm MB}(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'_{\rm MB}(G)$ and $S'_{\rm MB}(G)$. Invariants $R_{\rm MB}(G)$, $R'_{\rm MB}(G)$, $S_{\rm MB}(G)$, and $S'_{\rm MB}(G)$ are compared among themselves and with the metric dimension ${\rm dim}(G)$. A large class of graphs $G$ is constructed for which $R_{\rm MB}(G) > {\rm dim}(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_{\rm MB}(G)$ and $R'_{\rm MB}(G)$ (or $S_{\rm MB}(G)$ and $S'_{\rm MB}(G)$), are determined for several graph classes, including trees, complete multi-partite graphs, grid graphs, and torus grid graphs.