The Library
Odd and even cycles in Maker–Breaker games
Tools
Bednarska, Małgorzata and Pikhurko, Oleg (2008) Odd and even cycles in Maker–Breaker games. European Journal of Combinatorics, Vol.29 (No.3). pp. 742-745. doi:10.1016/j.ejc.2007.02.017 ISSN 0195-6698.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.ejc.2007.02.017
Abstract
Let Maker and Breaker alternately select respectively 1 and q previously unclaimed edges of Kn until all edges have been claimed. In the even cycle game Maker’s aim is to create an even cycle. We show that if View the MathML source, then Maker has a winning strategy. This is asymptotically matched by a previous result of the authors [M. Bednarska, O. Pikhurko, Biased positional games on matroids, Eur. J. Combin. 26 (2005) 271–285] that if q≥⌈n/2⌉−1 then Breaker can ensure that Maker’s graph is acyclic. We also consider the odd cycle game and show that for View the MathML source Maker can create an odd cycle.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | European Journal of Combinatorics | ||||
Publisher: | Academic Press | ||||
ISSN: | 0195-6698 | ||||
Official Date: | April 2008 | ||||
Dates: |
|
||||
Volume: | Vol.29 | ||||
Number: | No.3 | ||||
Number of Pages: | 4 | ||||
Page Range: | pp. 742-745 | ||||
DOI: | 10.1016/j.ejc.2007.02.017 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Funder: | KBN, Berkman Faculty Development Fund, Carnegie Mellon University, National Science Foundation (NSF) | ||||
Grant number: | 2 P03A 016 23, DMS-0457512 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |