Cycle-Free Saturation Games*

Abstract: It's all fun and games until someone loses a subgraph! Originally proposed by Hajnal, the saturation game involves two players, Mini and Maxi, who take turns adding single edges to a graph with $n$ vertices and no edges. Each player has their own goal to minimize or maximize, respectively, the number of edges in the graph when the game ends. Throughout the game, both players must place their edges in such a way that no subgraph of $G$ is isomorphic to any graph $F\in \mathcal{F}$ for some family of forbidden graphs $\mathcal{F}$. The game ends when adding any edge to $G$ would create some forbidden subgraph. More formally we say that $G$ is $\textit{$F$-saturated}$, if no subgraph of $G$ is isomorphic to any graph $F\in \mathcal{F}$, but for any edge $e$ not in $G$ there is some subgraph of $G+e$ in $\mathcal{F}$. When playing this $\textit{Saturation Game}$ we assume that both Mini and Maxi play optimally. We define the $\textit{game saturation number of the graph},$ denoted $\mathrm{sat}_G(n; \mathcal{F})$ to be the number of edges at the end of the game. In this talk we consider the particular game where we forbid odd cycles. Specifically, we consider forbidding all odd cycles other than triangles and denote $\mathcal{F} = \mathcal{C}_{\infty}^O \backslash { C_3}$. We will discuss particular strategies of each player, and bound the game saturation number in a variety of cases. Along the way, we will define and make use of a graph property that we call $\textit{$k$-fantastic}.$ We'll conclude with a linear upper bound for the odd cycle saturation games in general.

Back to Search Research Symposium Abstracts