Strong games played on random graphs

Publication date 17 February 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.04229, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p35

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

perfect matching positional games random graphs

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Positional games (pursuit and evasion, etc.) (91A24) Games involving graphs (91A43)

Abstract: In a strong game played on the edge set of a graph G there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of G (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique, a perfect matching, a Hamilton cycle, etc.). It is well known that Red can always ensure at least a draw in any strong game, but finding explicit winning strategies is a difficult and a quite rare task. We consider strong games played on the edge set of a random graph G ~ G(n,p) on n vertices. We prove, for sufficiently large

n

and a fixed constant 0 < p < 1, that Red can w.h.p win the perfect matching game on a random graph G ~ G(n,p).

Review text

Summary: In a strong game played on the edge set of a graph \(G\) there are two players, Red and Blue, alternating turns in claiming previously unclaimed edges of \(G\) (with Red playing first). The winner is the first one to claim all the edges of some target structure (such as a clique \(K_k\), a perfect matching, a Hamilton cycle, etc.). In this paper we consider strong games played on the edge set of a random graph \(G~ G(n,p)\) on \(n\) vertices. We prove that \(G\sim G(n,p)\) is typically such that Red can win the perfect matching game played on \(E(G)\), provided that \(p\in(0,1)\) is a fixed constant.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Strong games played on random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q510354)