Abstract
A 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/(ln n)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.
Original language | English (US) |
---|---|
Pages (from-to) | 369-389 |
Number of pages | 21 |
Journal | Random Structures and Algorithms |
Volume | 35 |
Issue number | 3 |
DOIs | |
State | Published - Oct 2009 |
Keywords
- Diameter
- Positional games
- Random graphs
ASJC Scopus subject areas
- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics