论文标题
Fenvaless比赛游戏
The Enclaveless Competition Game
论文作者
论文摘要
对于图$ g $中的子集$ s $，如果$ v $，则$ s $的顶点$ v \是$ s $的飞越，其所有邻居都在$ s $中，其中$ v $的邻居是$ v $的顶点。如果不包含任何飞地，则设置$ s $是范围的。 $ g $的Fendaveless编号$ψ（g）$是$ g $的封装设置的最大基数。正如Slater在1997年首次观察的那样[J. res。纳特。伯。标准82（1977），197--202]，如果$ g $是带有$ n $顶点的图形，则$γ（g） +ψ（g）= n $，其中$γ（g）$是$ g $的$γ（g）$。在本文中，我们继续研究Phillips and Slater在2001年推出的竞争 - 魅力游戏[Graph Doemens Notes N. Y. 41（2001），37--41]，并定义如下。两名玩家轮流构建最大围墙集$ s $，其中一个玩家，最大化器试图最大化$ | s | $，一个玩家，最小化器，尝试最小化〜$ | s | $。 $ g $的竞赛 - 振动游戏编号$ψ_g^+（g）$是当Maximizer启动游戏时播放的顶点数量，并且两个玩家都在最佳比赛中发挥。我们在其他问题中研究了一个猜想，如果$ g $是$ n $的孤立图，则$ψ_g^+（g）\ ge \ frac {1} {2} {2} n $。我们证明了常规图和无爪图的猜想。
For a subset $S$ of vertices in a graph $G$, a vertex $v \in S$ is an enclave of $S$ if $v$ and all of its neighbors are in $S$, where a neighbor of $v$ is a vertex adjacent to $v$. A set $S$ is enclaveless if it does not contain any enclaves. The enclaveless number $Ψ(G)$ of $G$ is the maximum cardinality of an enclaveless set in $G$. As first observed in 1997 by Slater [J. Res. Nat. Bur. Standards 82 (1977), 197--202], if $G$ is a graph with $n$ vertices, then $γ(G) + Ψ(G) = n$ where $γ(G)$ is the well-studied domination number of $G$. In this paper, we continue the study of the competition-enclaveless game introduced in 2001 by Phillips and Slater [Graph Theory Notes N. Y. 41 (2001), 37--41] and defined as follows. Two players take turns in constructing a maximal enclaveless set $S$, where one player, Maximizer, tries to maximize $|S|$ and one player, Minimizer, tries to minimize~$|S|$. The competition-enclaveless game number $Ψ_g^+(G)$ of $G$ is the number of vertices played when Maximizer starts the game and both players play optimally. We study among other problems the conjecture that if $G$ is an isolate-free graph of order $n$, then $Ψ_g^+(G) \ge \frac{1}{2}n$. We prove this conjecture for regular graphs and for claw-free graphs.
