Saturation games for odd cycles

Publication date 14 October 2019

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

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

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

\(\mathcal{F}\)-saturation game \(\{C_3\}\)-saturation game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) 2-person games (91A05) Games involving graphs (91A43)

Abstract: Given a family of graphs

m a t h c a l F

, we consider the

m a t h c a l F

-saturation game. In this game two players alternate adding edges to an initially empty graph on

n

vertices, with the only constraint being that neither player can add an edge that creates a subgraph that lies in

m a t h c a l F

. The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let

s a t_{g} (m a t h c a l F; n)

denote the number of edges that are in the final graph when both players play optimally. The

C_{3}

-saturation game was the first saturation game to be considered, but as of now the order of magnitude of

s a t_{g} (C_{3}, n)

remains unknown. We consider a generalization of this game. Let

m a t h c a l C_{2 k + 1} := C_{3}, C_{5}, l d o t s, C_{2 k + 1}

. We prove that

s a t_{g} (m a t h c a l C_{2 k + 1}; n) g e (f r a c 14 - e p s i l o n_{k}) n^{2} + o (n^{2})

for all

k g e 2

and that

s a t_{g} (m a t h c a l C_{2 k + 1}; n) l e (f r a c 14 - e p s i l o n'_{k}) n^{2} + o (n^{2})

for all

k g e 4

, with

e p s i l o n_{k} < f r a c 14

and

e p s i l o n'_{k} > 0

constants tending to 0 as

k o i n f t y

. In addition to this we prove

s a t_{g} (C_{2 k + 1}; n) l e f r a c 427 n^{2} + o (n^{2})

for all

k g e 2

, and

s a t_{g} (m a t h c a l C_{i} n f t y s e t m i n u s C_{3}; n) l e 2 n - 2

, where

m a t h c a l C_{i} n f t y

denotes the set of all odd cycles.

Review text

Summary: Given a family of graphs \(\mathcal{F}\), we consider the \(\mathcal{F}\)-saturation game. In this game, two players alternate adding edges to an initially empty graph on \(n\) vertices, with the only constraint being that neither player can add an edge that creates a subgraph that lies in \(\mathcal{F}\). The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let \(\text{sat}_g(\mathcal{F};n)\) denote the number of edges that are in the final graph when both players play optimally. Given a family of graphs \(\mathcal{F}\), we consider the \(\mathcal{F}\)-saturation game. In this game, two players alternate adding edges to an initially empty graph on \(n\) vertices, with the only constraint being that neither player can add an edge that creates a subgraph that lies in \(\mathcal{F}\). The game ends when no more edges can be added to the graph. One of the players wishes to end the game as quickly as possible, while the other wishes to prolong the game. We let \(\text{sat}_g(\mathcal{F};n)\) denote the number of edges that are in the final graph when both players play optimally. The \(\{C_3\}\)-saturation game was the first saturation game to be considered, but as of now the order of magnitude of \(\operatorname{sat}_g(\{C_3\},n)\) remains unknown. We consider a variation of this game. Let \(\mathcal{C}_{2k+1}:=\{C_3,\ C_5,\ldots,C_{2k+1}\}\). We prove that \(\operatorname{sat}_g(\mathcal{C}_{2k+1};n)\ge(\frac{1}{4}-\varepsilon_k)n^2+o(n^2)\) for all \(k\ge 2\) and that \(\operatorname{sat}_g(\mathcal{C}_{2k+1};n)\le (\frac{1}{4}-\varepsilon'_k)n^2+o(n^2)\) for all \(k\ge 4\), with \(\varepsilon_k<\frac{1}{4}\) and \(\varepsilon'_k>0\) constants tending to 0 as \(k\to \infty\). In addition to this we prove \(\operatorname{sat}_g(\{C_{2k+1}\};n)\le \frac{4}{27}n^2+o(n^2)\) for all \(k\ge 2\), and \(\operatorname{sat}_g(\mathcal{C}_\infty\setminus C_3;n)\le 2n-2\), where \(\mathcal{C}_\infty\) denotes the set of all odd cycles.

Recommendations

Cites work

Cited in

(8)

This page was built for publication: Saturation games for odd cycles

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