×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] P. Bennett T. Bohman A note on the random greedy independent set algorithm · Zbl 1349.05314
[2] 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
[3] 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
[4] Bollobás, Constrained graph processes, Electron J Comb 7 (2000)
[5] Cranston, Game matching number of graphs, Discrete Appl Math 161 pp 1828– (2013) · Zbl 1286.05133 · doi:10.1016/j.dam.2013.03.010
[6] Erdos, A problem in graph theory, Am Math Mon 71 pp 1107– (1964) · Zbl 0126.39401 · doi:10.2307/2311408
[7] 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
[8] Erdos, On the size of a random maximal graph, Random Struct Algorithms 6 pp 309– (1995) · Zbl 0820.05054 · doi:10.1002/rsa.3240060217
[9] Faudree, A survey of minimum saturated graphs, Electron J Combin 18 (2011) · Zbl 1222.05113
[10] Feldheim, Winning fast in sparse graph construction games, Combin Probab Comput 17 (6) pp 781– (2008) · Zbl 1169.91320 · doi:10.1017/S0963548308009401
[11] 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
[12] 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
[13] 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
[14] Z. Füredi D. Reimer Á. Seress Hajnal’s triangle-free game and extremal graph problems 82 1991 123 128
[15] Hefetz, Europ J Comb 51 (2016) · Zbl 1321.05158 · doi:10.1016/j.ejc.2015.05.017
[16] Hefetz, Planarity, colorability, and minor games, SIAM J Discrete Math 22 (1) pp 194– (2008) · Zbl 1167.91010 · doi:10.1137/060654414
[17] 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
[18] 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
[19] J. D. Lee A.-E. Riet F -saturation games 338 2015 2356 2362
[20] Osthus, Maximal H-free graphs, Random Struct, Algorithms 18 pp 61– (2001)
[21] Patkós, Game saturation of intersecting families, Cent. Eur J Math 12 (9) pp 1382– (2014)
[22] 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.