Geodesic
Linear bounds for cycle-free saturation games
Sean English1 ; Tomáš Masařík2 ; Grace McCourt1 ; Erin Meger3 ; Michael S. Ross4 ; Sam Spiro5
1University of Illinois at Urbana-Champaign
2University of Warsaw
3Concordia University
4Iowa State University
5UC San Diego
The electronic journal of combinatorics, Tome 29 (2022) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Given a family of graphs $\mathcal{F}$, we define the $\mathcal{F}$-saturation game as follows. 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 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 $\textrm{sat}_g(n,\mathcal{F})$ denote the number of edges that are in the final graph when both players play optimally.In general there are very few non-trivial bounds on the order of magnitude of $\textrm{sat}_g(n,\mathcal{F})$. In this work, we find collections of infinite families of cycles $\mathcal{C}$ such that $\textrm{sat}_g(n,\mathcal{C})$ has linear growth rate.
DOI : 10.37236/10808
Classification : 05C57, 05C35, 05C38, 91A43, 91A05
Mots-clés : saturation number, \(\mathcal{F}\)-saturation game

Sean English  1   ; Tomáš Masařík  2   ; Grace McCourt  1   ; Erin Meger  3   ; Michael S. Ross  4   ; Sam Spiro  5

1 University of Illinois at Urbana-Champaign
2 University of Warsaw
3 Concordia University
4 Iowa State University
5 UC San Diego 
@article{10_37236_10808,
     author = {Sean English and Tom\'a\v{s} Masa\v{r}{\'\i}k and Grace McCourt and Erin Meger and Michael S. Ross and Sam Spiro},
     title = {Linear bounds for cycle-free saturation games},
     journal = {The electronic journal of combinatorics},
     year = {2022},
     volume = {29},
     number = {3},
     doi = {10.37236/10808},
     zbl = {1492.05100},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/10808/}
}
TY  - JOUR
AU  - Sean English
AU  - Tomáš Masařík
AU  - Grace McCourt
AU  - Erin Meger
AU  - Michael S. Ross
AU  - Sam Spiro
TI  - Linear bounds for cycle-free saturation games
JO  - The electronic journal of combinatorics
PY  - 2022
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/10808/
DO  - 10.37236/10808
ID  - 10_37236_10808
ER  - 
%0 Journal Article
%A Sean English
%A Tomáš Masařík
%A Grace McCourt
%A Erin Meger
%A Michael S. Ross
%A Sam Spiro
%T Linear bounds for cycle-free saturation games
%J The electronic journal of combinatorics
%D 2022
%V 29
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/10808/
%R 10.37236/10808
%F 10_37236_10808
Sean English; Tomáš Masařík; Grace McCourt; Erin Meger; Michael S. Ross; Sam Spiro. Linear bounds for cycle-free saturation games. The electronic journal of combinatorics, Tome 29 (2022) no. 3. doi: 10.37236/10808

Cité par Sources :