{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T16:54:00Z","timestamp":1675356840655},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2013,11,4]],"date-time":"2013-11-04T00:00:00Z","timestamp":1383523200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We study the (1:<jats:italic>b<\/jats:italic>) Maker\u2013Breaker component game, played on the edge set of a<jats:italic>d<\/jats:italic>-regular graph. Maker's aim in this game is to build a large connected component, while Breaker's aim is to prevent him from doing so. For all values of Breaker's bias<jats:italic>b<\/jats:italic>, we determine whether Breaker wins (on any<jats:italic>d<\/jats:italic>-regular graph) or Maker wins (on almost every<jats:italic>d<\/jats:italic>-regular graph) and provide explicit winning strategies for both players.<\/jats:p><jats:p>To this end, we prove an extension of a theorem of Gallai, Hasse, Roy and Vitaver about graph orientations without long directed simple paths.<\/jats:p>","DOI":"10.1017\/s0963548313000527","type":"journal-article","created":{"date-parts":[[2013,11,4]],"date-time":"2013-11-04T11:02:33Z","timestamp":1383562953000},"page":"75-89","source":"Crossref","is-referenced-by-count":1,"title":["Component Games on Regular Graphs"],"prefix":"10.1017","volume":"23","author":[{"given":"RANI","family":"HOD","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALON","family":"NAOR","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,11,4]]},"reference":[{"key":"S0963548313000527_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20059"},{"key":"S0963548313000527_ref19","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/1967010501291"},{"key":"S0963548313000527_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20279"},{"key":"S0963548313000527_ref13","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"S0963548313000527_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2010.09.005"},{"key":"S0963548313000527_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"S0963548313000527_ref8","first-page":"115","volume-title":"Theory of Graphs: Proc. Colloq. Tihany 1966","author":"Gallai","year":"1968"},{"key":"S0963548313000527_ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0112059"},{"key":"S0963548313000527_ref21","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.221"},{"key":"S0963548313000527_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(78)90102-4"},{"key":"S0963548313000527_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200103)18:2<141::AID-RSA1002>3.0.CO;2-W"},{"key":"S0963548313000527_ref6","first-page":"251","article-title":"Regular graphs with given girth and minimal number of knots (in German).","volume":"12","author":"Erd\u0151s","year":"1963","journal-title":"Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss"},{"key":"S0963548313000527_ref22","first-page":"758","article-title":"Determination of minimal colouring of vertices of a graph by means of Boolean powers of the incidence matrix (in Russian).","volume":"147","author":"Vitaver","year":"1962","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0963548313000527_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19650280503"},{"key":"S0963548313000527_ref1","doi-asserted-by":"publisher","DOI":"10.1017\/S096354839700299X"},{"key":"S0963548313000527_ref7","doi-asserted-by":"crossref","unstructured":"Ferber A. , Glebov R. , Krivelevich M. and Naor A. Biased games on random boards. Random Struct. Alg., to appear.","DOI":"10.1002\/rsa.20528"},{"key":"S0963548313000527_ref14","unstructured":"Hod R. , Krivelevich M. , M\u00fcller T. and Naor A. Component games on random graphs. In preparation."},{"key":"S0963548313000527_ref12","doi-asserted-by":"crossref","first-page":"P61","DOI":"10.37236\/2129","article-title":"Doubly biased Maker-Breaker Connectivity game","volume":"19","author":"Hefetz","year":"2012","journal-title":"Electron. J. Combin."},{"key":"S0963548313000527_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20277"},{"key":"S0963548313000527_ref2","doi-asserted-by":"crossref","first-page":"1727","DOI":"10.1214\/009117904000000414","article-title":"Percolation on finite graphs and isoperimetric inequalities.","volume":"32","author":"Alon","year":"2004","journal-title":"Ann. Probab."},{"key":"S0963548313000527_ref18","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-36.1.445"},{"key":"S0963548313000527_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70335-2"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000527","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,7]],"date-time":"2020-08-07T09:18:35Z","timestamp":1596791915000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000527\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11,4]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["S0963548313000527"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000527","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11,4]]}}}