论文标题
避免星星游戏
The star avoidance game
论文作者
论文摘要
令$ n，k $为积极的整数。 $（k+1）$ - $ k_n $上的星星避免游戏如下。两名玩家依次将其索取了$ n $顶点的完整图的（以前无人认领的）边缘。第一个要求$（k+1）$ - 星星损失的子图同构的所有边缘的玩家。同等地，每个玩家必须将所有学位保留在其边缘最多$ k $的子图中。如果选择了所有边缘，并且两者都没有输掉，则该游戏被宣布为平局。我们证明，对于每个固定的$ k $，对于所有$ n $来说，游戏都是第二个玩家的胜利。
Let $n, k$ be positive integers. The $(k+1)$-star avoidance game on $K_n$ is played as follows. Two players take it in turn to claim a (previously unclaimed) edge of the complete graph on $n$ vertices. The first player to claim all edges of a subgraph isomorphic to a $(k+1)$-star loses. Equivalently, each player must keep all degrees in the subgraph formed by his edges at most $k$. If all edges have been chosen and neither player has lost, the game is declared a draw. We prove that, for each fixed $k$, the game is a win for the second player for all $n$ sufficiently large.
