
arXiv: 1405.2834
AbstractGiven a family and a host graph H, a graph is ‐saturated relative to H if no subgraph of G lies in but adding any edge from to G creates such a subgraph. In the ‐saturation game on H, players Max and Min alternately add edges of H to G, avoiding subgraphs in , until G becomes ‐saturated relative to H. They aim to maximize or minimize the length of the game, respectively; denotes the length under optimal play (when Max starts).Let denote the family of odd cycles and the family of n‐vertex trees, and write F for when . Our results include , for , for , and for . We also determine ; with , it is n when n is even, m when n is odd and m is even, and when is odd. Finally, we prove the lower bound . The results are very similar when Min plays first, except for the P4‐saturation game on .
spanning tree, Games on graphs (graph-theoretic aspects), saturation number, forbidden subgraph, 004, 05C35 (Primary) 05C57 (Secondary), graph game, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs
spanning tree, Games on graphs (graph-theoretic aspects), saturation number, forbidden subgraph, 004, 05C35 (Primary) 05C57 (Secondary), graph game, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Games involving graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
