Linear Bounds for Cycle-Free Saturation Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455176" target="_blank" >RIV/00216208:11320/22:10455176 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=goUf~N_94m" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=goUf~N_94m</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.37236/10808" target="_blank" >10.37236/10808</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Linear Bounds for Cycle-Free Saturation Games

Popis výsledku v původním jazyce

Given a family of graphs F, we define the 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 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 sat(g)(n, 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 sat(g)(n, F). In this work, we find collections of infinite families of cycles C such that sat(g)(n, C) has linear growth rate.

Název v anglickém jazyce

Linear Bounds for Cycle-Free Saturation Games

Popis výsledku anglicky

Given a family of graphs F, we define the 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 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 sat(g)(n, 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 sat(g)(n, F). In this work, we find collections of infinite families of cycles C such that sat(g)(n, C) has linear growth rate.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1077-8926

e-ISSN

—

Svazek periodika

29

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

21

Strana od-do

P3.5

Kód UT WoS článku

000822527000001

EID výsledku v databázi Scopus

2-s2.0-85133618680