# zbMATH — the first resource for mathematics

The game saturation number of a graph. (English) Zbl 1365.05195
Summary: Given a family $$\mathcal{F}$$ and a host graph $$H$$, a graph $$G\subseteq H$$ is $$\mathcal{F}$$-saturated relative to $$H$$ if no subgraph of $$G$$ lies in $$\mathcal{F}$$ but adding any edge from $$E(H)-E(G)$$ to $$G$$ creates such a subgraph. In the $$\mathcal{F}$$-saturation game on $$H$$, players Max and Min alternately add edges of $$H$$ to $$G$$, avoiding subgraphs in $$\mathcal{F}$$, until $$G$$ becomes $$\mathcal{F}$$-saturated relative to $$H$$. They aim to maximize or minimize the length of the game, respectively; $$\mathrm{sat}_g(\mathcal{F};H)$$ denotes the length under optimal play (when Max starts).
Let $$\mathcal{O}$$ denote the family of odd cycles and $$\mathcal{T}_n$$ the family of $$n$$-vertex trees, and write $$F$$ for $$\mathcal{F}$$ when $$\mathcal{F}=\{F\}$$. Our results include $$\mathrm{sat}_g(\mathcal{O};K_n)=\lfloor\frac n2\rfloor\lceil\frac n2\rceil,\;\mathrm{sat}_g(\mathcal{I}_n;K_n)=\tbinom{n-2}{2}+1$$ for $$n\geq6,\;\mathrm{sat}_g(K_{1,3};K_n)=2\lfloor\frac n2\rfloor$$ for $$n\geq8$$, and $$\mathrm{sat}_g(P_4;K_n)\in\{\lfloor\frac{4n}5\rfloor,\lceil\frac{4n}5\rceil\}$$ for $$n\geq5$$. We also determine $$\mathrm{sat}_g(P_4;K_{m,n})$$; with $$m\geq n$$, it is $$n$$ when $$n$$ is even, $$m$$ when $$n$$ is odd and $$m$$ is even, and $$m+\lfloor n/2\rfloor$$ when $$mn$$ is odd. Finally, we prove the lower bound $$\mathrm{sat}_g(C_4;K_{n,n})\geq\frac1{21}n^{13/12}-O(n^{35/36})$$. The results are very similar when Min plays first, except for the $$P_4$$-saturation game on $$K_{m,n}$$.

##### MSC:
 05C57 Games on graphs (graph-theoretic aspects) 91A43 Games involving graphs
##### Keywords:
saturation number; graph game; forbidden subgraph; spanning tree
Full Text:
##### References:
  P. Bennett T. Bohman A note on the random greedy independent set algorithm · Zbl 1349.05314  Biró, An upper bound on the extremal version of Hajnal’s triangle-free game, Discrete Appl Math 198 pp 20– (2016) · Zbl 1326.05091 · doi:10.1016/j.dam.2015.06.031  Bohman, The early evolution of the H-free process, Invent Math 181 (2) pp 291– (2010) · Zbl 1223.05270 · doi:10.1007/s00222-010-0247-x  Bollobás, Constrained graph processes, Electron J Comb 7 (2000)  Cranston, Game matching number of graphs, Discrete Appl Math 161 pp 1828– (2013) · Zbl 1286.05133 · doi:10.1016/j.dam.2013.03.010  Erdos, A problem in graph theory, Am Math Mon 71 pp 1107– (1964) · Zbl 0126.39401 · doi:10.2307/2311408  Erdos, Intersection theorems for systems of finite sets, Quart J Math Oxford Ser 12 (2) pp 313– (1961) · Zbl 0100.01902 · doi:10.1093/qmath/12.1.313  Erdos, On the size of a random maximal graph, Random Struct Algorithms 6 pp 309– (1995) · Zbl 0820.05054 · doi:10.1002/rsa.3240060217  Faudree, A survey of minimum saturated graphs, Electron J Combin 18 (2011) · Zbl 1222.05113  Feldheim, Winning fast in sparse graph construction games, Combin Probab Comput 17 (6) pp 781– (2008) · Zbl 1169.91320 · doi:10.1017/S0963548308009401  Ferrara, The game of F-saturator, Discrete Appl Math 158 (3) pp 189– (2010) · Zbl 1226.05179 · doi:10.1016/j.dam.2009.09.014  Füredi, On maximal intersecting families of finite sets, J Combin Theory Ser. A 28 (3) pp 282– (1980) · Zbl 0438.05002 · doi:10.1016/0097-3165(80)90071-0  Füredi, New asymptotics for bipartite Turán numbers, J Combin Theory Ser. A 75 (1) pp 141– (1996) · Zbl 0858.05064 · doi:10.1006/jcta.1996.0067  Z. Füredi D. Reimer Á. Seress Hajnal’s triangle-free game and extremal graph problems 82 1991 123 128  Hefetz, Europ J Comb 51 (2016) · Zbl 1321.05158 · doi:10.1016/j.ejc.2015.05.017  Hefetz, Planarity, colorability, and minor games, SIAM J Discrete Math 22 (1) pp 194– (2008) · Zbl 1167.91010 · doi:10.1137/060654414  Hefetz, Fast winning strategies in Maker-Breaker games, J Combin Theory Ser. B 99 (1) pp 39– (2009) · Zbl 1214.05062 · doi:10.1016/j.jctb.2008.04.001  Kászonyi, Saturated graphs with minimal number of edges, J. Graph Theory 10 (2) pp 203– (1986) · Zbl 0593.05041 · doi:10.1002/jgt.3190100209  J. D. Lee A.-E. Riet F -saturation games 338 2015 2356 2362  Osthus, Maximal H-free graphs, Random Struct, Algorithms 18 pp 61– (2001)  Patkós, Game saturation of intersecting families, Cent. Eur J Math 12 (9) pp 1382– (2014)  Turán, Eine Extremalaufgabe aus der Graphentheorie, Mat Fiz Lapok 48 pp 436– (1941)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.