
arXiv: 1605.05698
AbstractA large class of Positional Games are defined on the complete graph on n vertices. The players, Maker and Breaker, take the edges of the graph in turns, and Maker wins iff his subgraph has a given — usually monotone — property. Here we introduce the d‐diameter game, which means that Maker wins iff the diameter of his subgraph is at most d. We investigate the biased version of the game; i.e., when the players may take more than one, and not necessarily the same number of edges, in a turn. Our main result is that we proved that the 2‐diameter game has the following surprising property: Breaker wins the game in which each player chooses one edge per turn, but Maker wins as long as he is permitted to choose 2 edges in each turn whereas Breaker can choose as many as (1/9)n1/8/(lnn)3/8. In addition, we investigate d‐diameter games for d ≥ 3. The diameter games are strongly related to the degree games. Thus, we also provide a generalization of the fair degree game for the biased case. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009
positional games, Distance in graphs, Games on graphs (graph-theoretic aspects), Random graphs (graph-theoretic aspects), 05C65, 91A43, 91A46, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, diameter, Positional games (pursuit and evasion, etc.), random graphs
positional games, Distance in graphs, Games on graphs (graph-theoretic aspects), Random graphs (graph-theoretic aspects), 05C65, 91A43, 91A46, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs, diameter, Positional games (pursuit and evasion, etc.), random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
