论文标题
制造商 - 破坏者公制的图表上的游戏
Maker-Breaker Metric Resolving Games on Graphs
论文作者
论文摘要
令$ d（x，y）$表示$ x $ x $和$ y $之间的最短路径的长度，而$ g $带有顶点set $ v $。对于正整数$ k $，令$ d_k（x，y）= \ min \ {d（x，y），k+1 \} $和$ r_k \ {x，y \} = \ {z \ in v：d_k（x，x，z）如果$ s \ $ k $ subseteq v $是$ g $的a \ emph {distair- $ k $ nesolving set}，如果$ s \ cap r_k \ {x，y \} \ neq \ neq \ neq \ neq \ emberySet $ for Disti则$ x，y \ in V $中。在本文中，我们研究了两个玩家，Maker and Breaker在图$ G $上玩的制造商 - $ K $分辨游戏（MB $ K $ RG），他们交替选择尚未选择的$ G $的顶点。制造商通过选择形成距离$ k $ $ g $的距离的顶点来获胜，而断路器通过防止制造商获胜而获胜。我们用$ o_ {r，k}（g）$表示MB $ K $ RG的结果。令$ \ Mathcal {M} $，$ \ Mathcal {B} $和$ \ Mathcal {n} $分别表示制造商，Breaker和第一个玩家在MB $ K $ RG中具有获胜策略的结果。给定图形$ g $，参数$ o_ {r，k}（g）$是$ k $的非淘汰函数，带有codomain $ \ { - 1 = \ mathcal {b}，0 = \ mathcal {n}，1 = \ Mathcal {M {m} \} $。我们展示对$ g $和$ k $，使得有序的一对$（o_ {r，k}（g），o_ {r，k+1}（g））$实现了集合$ \ {（\ Mathcal {b}的每个成员， \ Mathcal {M}），（\ Mathcal {n}，\ Mathcal {M}）\} $;我们提供图形$ g $，以便$ o_ {r，1}（g）= \ nathcal {b} $，$ o_ {r，2}（g）= \ nathcal {n} $和$ o_ {r，k}（r，k}（g）= \ nathcal {m} $ k \ k \ ge3 $。此外，我们在MB $ K $ RG上获得了一些一般结果，并研究了某些图表上播放的MB $ K $ RG。
Let $d(x,y)$ denote the length of a shortest path between vertices $x$ and $y$ in a graph $G$ with vertex set $V$. For a positive integer $k$, let $d_k(x,y)=\min\{d(x,y), k+1\}$ and $R_k\{x,y\}=\{z\in V: d_k(x,z) \neq d_k(y,z)\}$. A set $S \subseteq V$ is a \emph{distance-$k$ resolving set} of $G$ if $S \cap R_k\{x,y\} \neq\emptyset$ for distinct $x,y\in V$. In this paper, we study the maker-breaker distance-$k$ resolving game (MB$k$RG) played on a graph $G$ by two players, Maker and Breaker, who alternately select a vertex of $G$ not yet chosen. Maker wins by selecting vertices which form a distance-$k$ resolving set of $G$, whereas Breaker wins by preventing Maker from winning. We denote by $O_{R,k}(G)$ the outcome of MB$k$RG. Let $\mathcal{M}$, $\mathcal{B}$ and $\mathcal{N}$, respectively, denote the outcome for which Maker, Breaker, and the first player has a winning strategy in MB$k$RG. Given a graph $G$, the parameter $O_{R,k}(G)$ is a non-decreasing function of $k$ with codomain $\{-1=\mathcal{B}, 0=\mathcal{N}, 1=\mathcal{M}\}$. We exhibit pairs $G$ and $k$ such that the ordered pair $(O_{R,k}(G), O_{R, k+1}(G))$ realizes each member of the set $\{(\mathcal{B}, \mathcal{N}),(\mathcal{B}, \mathcal{M}),(\mathcal{N},\mathcal{M})\}$; we provide graphs $G$ such that $O_{R,1}(G)=\mathcal{B}$, $O_{R,2}(G)=\mathcal{N}$ and $O_{R,k}(G)=\mathcal{M}$ for $k\ge3$. Moreover, we obtain some general results on MB$k$RG and study the MB$k$RG played on some graph classes.
