Hostname: page-component-745bb68f8f-kw2vx Total loading time: 0 Render date: 2025-02-06T15:46:06.299Z Has data issue: false hasContentIssue false
  • English
  • Français

Component Games on Regular Graphs

Published online by Cambridge University Press:  04 November 2013

RANI HOD  and
ALON NAOR
RANI HOD
Affiliation:
School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: rani.hod@cs.tau.ac.il)
ALON NAOR
Affiliation:
School of Mathematical Sciences, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel (e-mail: alonnaor@tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the (1:b) Maker–Breaker component game, played on the edge set of a d-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 b, we determine whether Breaker wins (on any d-regular graph) or Maker wins (on almost every d-regular graph) and provide explicit winning strategies for both players.

To this end, we prove an extension of a theorem of Gallai, Hasse, Roy and Vitaver about graph orientations without long directed simple paths.

Keywords

Primary 91A24Secondary 05C57
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 1 , January 2014 , pp. 75 - 89
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Alon, N. (1997) On the edge-expansion of graphs. Combin. Probab. Comput. 6 145–152.CrossRefGoogle Scholar
[2]Alon, N., Benjamini, I. and Stacey, A. (2004) Percolation on finite graphs and isoperimetric inequalities. Ann. Probab. 32 1727–1745.CrossRefGoogle Scholar
[3]Bednarska, M. and Łuczak, T. (2001) Biased positional games and the phase transition. Random Struct. Alg. 18 141–152.Google Scholar
[4]Bollobás, B. (1978) Chromatic number, girth and maximal degree. Discrete Math. 24 311–314.CrossRefGoogle Scholar
[5]Chvátal, V. and Erdős, P. (1978) Biased positional games. Ann. Discrete Math. 2 221–228.CrossRefGoogle Scholar
[6]Erdős, P. and Sachs, H. (1963) Regular graphs with given girth and minimal number of knots (in German). Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss 12 251–257.Google Scholar
[7]Ferber, A., Glebov, R., Krivelevich, M. and Naor, A. Biased games on random boards. Random Struct. Alg., to appear.Google Scholar
[8]Gallai, T. (1968) On directed graphs and circuits. In Theory of Graphs: Proc. Colloq. Tihany 1966, New York Academic Press, pp. 115–118.Google Scholar
[9]Gebauer, H. and Szabó, T. (2009) Asymptotic random graph intuition for the biased connectivity game. Random Struct. Alg. 35 431–443.CrossRefGoogle Scholar
[10]Hasse, M. (1965) Zur algebraischen Begründung der Graphentheorie I (in German). Mathematische Nachrichten 28 275–290.CrossRefGoogle Scholar
[11]Hefetz, D., Krivelevich, M., Stojaković, M. and Szabó, T. (2011) Global Maker–Breaker games on sparse graphs. Europ. J. Combin. 32 162–177.Google Scholar
[12]Hefetz, D., Mikalački, M. and Stojaković, M. (2012) Doubly biased Maker-Breaker Connectivity game. Electron. J. Combin. 19 P61.Google Scholar
[13]Hoory, S., Linial, N. and Wigderson, A. (2006) Expander graphs and their applications. Bull. Amer. Math. Soc. 43 439–561.Google Scholar
[14]Hod, R., Krivelevich, M., Müller, T. and Naor, A. Component games on random graphs. In preparation.Google Scholar
[15]Lehman, A. (1964) A solution of the Shannon switching game. J. Soc. Indust. Appl. Math. 12 687–725.CrossRefGoogle Scholar
[16]Lubotzky, A., Phillips, R. and Sarnak, P. (1988) Ramanujan graphs. Combinatorica 8 261–277.Google Scholar
[17]Nachmias, A. and Peres, Y. (2010) Critical percolation on random regular graphs. Random Struct. Alg. 36 111–148.Google Scholar
[18]Nash–Williams, C. St J. A. (1961) Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36 445–450.Google Scholar
[19]Roy, B. (1967) Nombre chromatique et plus longs chemins d'un graphe (in French). Rev. Française Informat. Recherche Opérationnelle 1 129–132.Google Scholar
[20]Stojaković, M. and Szabó, T. (2005) Positional games on random graphs. Random Struct. Alg. 26 204–223.Google Scholar
[21]Tutte, W. T. (1961) On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36 221–230.Google Scholar
[22]Vitaver, L. M. (1962) Determination of minimal colouring of vertices of a graph by means of Boolean powers of the incidence matrix (in Russian). Dokl. Akad. Nauk SSSR 147 758–759.Google Scholar