论文标题
在强大的避免比赛中
On strong avoiding games
论文作者
论文摘要
考虑到增加的图形属性$ \ cal f $，在完整图的边缘集中播放了强大的Avoider-avoider $ \ cal f $游戏。红色和蓝色的两名玩家轮流宣称先前无人认领的边缘，红色首先发行，其图形拥有$ \ cal f $首先失去了游戏。如果属性$ \ cal f $是“包含固定图$ h $”，我们将游戏称为$ h $游戏。 我们证明，Blue在两个强大的Avoider-avoider游戏中具有获胜策略，$ P_4 $游戏和$ {\ cal cc} _ {> 3} $ game，其中$ {\ cal cc} _ {> 3} $是至少在三个角度上具有至少一个连接组件的属性。 我们还研究了一个变种，强大的卡德维德游戏，并要求每个玩家的图表必须在整个游戏中保持联系。我们证明，Blue在强大的Cavoider-Cavoider Games $ s_3 $和$ p_4 $以及$ Cycle $ Game中具有成功的策略，玩家旨在避免所有周期。
Given an increasing graph property $\cal F$, the strong Avoider-Avoider $\cal F$ game is played on the edge set of a complete graph. Two players, Red and Blue, take turns in claiming previously unclaimed edges with Red going first, and the player whose graph possesses $\cal F$ first loses the game. If the property $\cal F$ is "containing a fixed graph $H$", we refer to the game as the $H$ game. We prove that Blue has a winning strategy in two strong Avoider-Avoider games, $P_4$ game and ${\cal CC}_{>3}$ game, where ${\cal CC}_{>3}$ is the property of having at least one connected component on more than three vertices. We also study a variant, the strong CAvoider-CAvoider games, with additional requirement that the graph of each of the players must stay connected throughout the game. We prove that Blue has a winning strategy in the strong CAvoider-CAvoider games $S_3$ and $P_4$, as well as in the $Cycle$ game, where the players aim at avoiding all cycles.
