## 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)n^{1/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
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics