On strong avoiding games

DOI10.1016/J.DISC.2022.113270zbMATH Open1505.91098arXiv2204.07971OpenAlexW4310072706MaRDI QIDQ2111931FDOQ2111931

Authors: Miloš Stojaković, Jelena Stratijev 

Publication date: 17 January 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Given an increasing graph property $calF$, the strong Avoider-Avoider $calF$ game is played on the edge set of a complete graph. Two players, Red and Blue, take turns in claiming previously unclaimed edges with Red going first, and the player whose graph possesses $calF$ first loses the game. If the property $calF$ is "containing a fixed graph $H$", we refer to the game as the $H$ game. We prove that Blue has a winning strategy in two strong Avoider-Avoider games, $P_4$ game and ${calCC}_{>3}$ game, where ${calCC}_{>3}$ is the property of having at least one connected component on more than three vertices. We also study a variant, the strong CAvoider-CAvoider games, with additional requirement that the graph of each of the players must stay connected throughout the game. We prove that Blue has a winning strategy in the strong CAvoider-CAvoider games $S_3$ and $P_4$, as well as in the $Cycle$ game, where the players aim at avoiding all cycles.

Full work available at URL: https://arxiv.org/abs/2204.07971

Recommendations

• Connected, bounded degree, triangle avoidance games
• On avoider-enforcer games
• Avoider-enforcer star games
• scientific article; zbMATH DE number 3900800
• scientific article; zbMATH DE number 1944410

zbMATH Keywords

games on graphspositional gamesavoidance gamessim

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Positional games
• Biased Positional Games
• Combinatorial Games
• Avoider-enforcer: the rules of the game
• Weak and strong \(k\)-connectivity games
• Walker-Breaker Games
• Winning strong games through fast strategies for weak games
• Graph Ramsey games
• Transitive avoidance games
• Title not available (Why is that?)
• Spanning Tree Game as Prim Would Have Played
• Title not available (Why is that?)
• On the WalkerMaker-WalkerBreaker games
• The star avoidance game
• The Game of Sim: A Winning Strategy for the Second Player

Cited In (3)

• On winning fast in Avoider-Enforcer games
• Title not available (Why is that?)
• Proper strong-Fibonacci games

This page was built for publication: On strong avoiding games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111931)