Originators: M. Ferrara, M. Jacobson, A. Harris, D.B. West (presented by James Carraher - REGS 2011)
Definitions: Let $\mathcal{F}$ be a family of graphs. A graph $G$ is $\mathcal{F}$-saturated if no subgraph of $G$ is in $\mathcal{F}$, but for any nonadjacent vertices $u$ and $v$ the graph obtained by adding $uv$ to $G$ does contain some member of $\mathcal{F}$. A graph $H$ is $\mathcal{F}$-saturated relative to $G$ if $H\subseteq G$, no subgraph of $H$ is in $\mathcal{F}$, and adding any edge of $E(G)-E(H)$ to $H$ creates a graph containing some member of $\mathcal{F}$. When $\mathcal{F}=\{F\}$, we write $F$-saturated instead of $\{F\}$-saturated.
Fix a graph $G$ and a family $\mathcal{F}$. The $\mathcal{F}$-saturation game on $G$ begins with the vertices of $G$ and none of its edges. Players $1$ and $2$ take turns adding edges of $G$ to the selected subgraph $H$. The first player forced to select an edge that results in $H$ containing some member of $\mathcal{F}$ loses. Alternatively the first player to make $H$ be $\mathcal{F}$-saturated relative to $G$ wins.
Background: The maximum and minimum number of edges in an $\mathcal F$-saturated graph with $n$ vertices are called the Turán number and saturation number of $\mathcal{F}$, written ex$(\mathcal{F},n)$ and sat$(\mathcal{F},n)$, respectively. The Turán number is well understood, but there are few graphs whose saturation number is known exactly. [EHM] determined the answer for $K_p$. [KT] introduced the general problem and proved a general upper bound. The values have also been determined for various trees [FFGJ], $tK_p$, $K_p\cup K_q$, generalized friendship graphs, books [CFG], $C_4$ [O], $C_5$ [C], and $K_{2,3}$ [PS]. Pikhurko [P] surveyed the early results, and $\mathcal F$-saturation was discussed in REGS in 2010 and 2009). General bounds for cycles in [BCEPST] and [GLS] have been improved by Füredi and Kim [FK].
The saturation number of $\mathcal F$ is the minimum size of a graph that is $\mathcal F$-saturated relative to $K_n$. The saturation game was introduced by Ferrera, Jacobson and Harris to study $\mathcal{F}$-saturated subgraphs of an arbitrary graph $G$.
Problem 1: Determine the winner of the $\mathcal{F}$-saturation game on $G$, for various $G$ and $\mathcal{F}$.
Results: Gallent, et al. [GGHR] solved the $P_3$-saturation game on $P_n$; it is even easier on $K_n$. Seress [Se] discussed the $K_3$-saturation game on $K_n$, calling it "Hajnal's Triangle-free Game"; he determined the winner under the restricted that the chosen edges always form a connected graph. In this case, Player 1 wins if and only if $n$ is even, and Seress conjectured that Player 1 wins the unrestricted game if and only if $n\equiv 2\mod 4$. Ferrara, Jacobson, and Harris [FJH] discuss the game for several graphs and families.
Problem 2: For a given graph $G$ and forbidden subgraph $F$, determine the minimum and maximum size of an $F$-saturated subgraph of $G$.
Alternate version: Problem 2 generalizes the Turán and saturation numbers from $K_n$ to an arbitrary host graph $G$. Since the chosen subgraph at the end of the game is always $\mathcal F$-saturated relative to $G$, the game suggests a problem in competitive optimization. Fix a graph $G$ and a family $\mathcal{F}$. Players Max and Min alternate selecting edges of $G$ for the chosen subgraph $H$. The game ends when $H$ is $\mathcal{F}$-saturated relative to $G$. Max wants the game to last as long as possible; Min wants to end it as quickly as possible. The game saturation number sat$\,_g(G,\mathcal{F})$ is the length of the game under optimal play by both players, with Max starting. With Min starting, the value under optimal play is sat$'_{g}(G,\mathcal{F})$. Many questions can be asked.
Problem 3: Determine the game saturation number for various $G$ and $\mathcal{F}$. Can the answer equal the minimum or maximum size of a subgraph that is $\mathcal F$-saturated relative to $G$? By how much can the value change depending on who starts?
Comments The $K_3$-saturation number of $K_n$ was studied by Furedi, Reimer, and Seress [FRS]. They proved that Max can ensure that the game lasts at least $(\frac12+o(1))n\lg n$ steps, and they attributed to Erdős a seemingly lost proof that Min can finish the game within $n^2/5$ steps. Biró, Horn, and Wildstrom [BHW] have announced an upper bound asymptotic to $\frac9{50}n^2$. The game $P_3$-saturation number of $G$ is simply the game matching number of $G$. REGS students have studied a number of instances of this game.
References:
[AFG] Amin, K; Faudree, J.; Gould, R.; Saturation numbers for
$K_4$-free graphs, in preparation.
[BCEPST] Barefoot, C. A.; Clark, L. H.; Entringer, R. C.; Porter, T. D.;
Székely, L. A.; Tuza, Zs. Cycle-saturated graphs of minimum size.
Selected papers in honour of Paul Erdős on the occasion of his 80th
birthday (Keszthely, 1993). Discrete Math. 150 (1996), no. 1-3, 31-48.
[BHW] Cs. Biró; P. Horn; D.J. Wildstrom; On Hajnal's triangle free game.
slides
[C] Chen, Ya-Chen; Minimum $C_5$-saturated graphs. J. Graph Theory 61
(2009), 111-126.
[CFG] Chen, Guantao; Faudree, Ralph J.; Gould, Ronald J. Saturation numbers of
books. Electron. J. Combin. 15 (2008), Research Paper 118, 12 pp.
[EHM] Erdős, P.; Hajnal, A.; Moon, J. W. A problem in graph theory. Amer.
Math. Monthly 71 1964 1107-1110.
[FFGJ] Faudree, J.R.; Faudree, R.J.; Gould, R.J; Jacobson, M.S;
Saturation numbers for trees,
Electron. J. Combin. 16 (2009), Research Paper 91, 19 pp.
[FJH] M. Ferrara, M. Jacobson, A. Harris. The game of $\mathcal F$-saturator.
Discrete Appl. Math. 158 (2010), no. 3, 189-197.
[FK] Z. Füredi and Y. Kim,
[FRS] Z. Füredi, D. Reimer, A. Seress. Triangle-Free Game and Extremal
Graph Problems. Congr. Numer. 82 (1991), 123-128.
[GGHR] R. Gallant, G. Gunther, B. Hartnell, D. Rall. A Game of Edge
Removal on Graphs. J. Comb. Math. Comb. Comp. 57 (2006), 75-82.
[GLS] Gould, Ronald; Łuczak, Tomasz; Schmitt, John; Constructive upper
bounds for cycle-saturated graphs of minimum size. Electron. J. Combin. 13
(2006), no. 1, Research Paper 29, 19 pp. (electronic).
[KT] Kászonyi, L.; Tuza, Zs. Saturated graphs with minimal number of
edges. J. Graph Theory 10 (1986), no. 2, 203-210.
[O] Ollmann, L. T. K2,2-saturated graphs with a minimal
number of edges. Proceedings of the Third Southeastern Conference on
Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton,
Fla., 1972), pp. 367-392. Florida Atlantic Univ., Boca Raton, Fla., 1972.
[P] Pikhurko, Oleg; Results and open problems on minimum saturated hypergraphs.
Ars Combin. 72 (2004), 111-127.
[PS] Pikhurko, Oleg; Schmitt, John; A note on minimum $K_{2,3}$-saturated
graphs. Australas. J. Combin. 40 (2008), 211-215.
[S] A. Seress. On Hajnal's triangle-free game. Graphs and Combin. 8
(1992) no. 1, 75-79.