Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/14173
Nаziv: | Fast winning strategies in Maker-Breaker games | Аutоri: | Hefetz D. Krivelevich M. Stojaković M. Szabó T. |
Dаtum izdаvаnjа: | 1-јан-2009 | Čаsоpis: | Journal of Combinatorial Theory. Series B | Sažetak: | We consider unbiased Maker-Breaker games played on the edge set of the complete graph Kn on n vertices. Quite a few such games were researched in the literature and are known to be Maker's win. Here we are interested in estimating the minimum number of moves needed for Maker in order to win these games. We prove the following results, for sufficiently large n: (1)Maker can construct a Hamilton cycle within at most n + 2 moves. This improves the classical bound of 2n due to Chvátal and Erdo{combining double acute accent}s [V. Chvátal, P. Erdo{combining double acute accent}s, Biased positional games, Ann. Discrete Math. 2 (1978) 221-228] and is almost tight;(2)Maker can construct a perfect matching (for even n) within n / 2 + 1 moves, and this is tight;(3)For a fixed k ≥ 3, Maker can construct a spanning k-connected graph within (1 + o (1)) k n / 2 moves, and this is obviously asymptotically tight. Several other related results are derived as well. © 2008 Elsevier Inc. All rights reserved. | URI: | https://open.uns.ac.rs/handle/123456789/14173 | ISSN: | 00958956 | DOI: | 10.1016/j.jctb.2008.04.001 |
Nаlаzi sе u kоlеkciјаmа: | FTN Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
44
prоvеrеnо 20.11.2023.
Prеglеd/i stаnicа
2
Prоtеklа nеdеljа
1
1
Prоtеkli mеsеc
0
0
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.