On strong avoiding games

DOI10.1016/J.DISC.2022.113270MaRDI QIDQ2111931zbMATH OpenOpenAlexFDO

Authors Miloš Stojaković, Jelena Stratijev

Publication date 17 January 2023

Published in Discrete Mathematics (Search for Journal in Brave)

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

games on graphs positional games avoidance games sim

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

Abstract: Given an increasing graph property

c a l F

, the strong Avoider-Avoider

c a l F

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

c a l F

first loses the game. If the property

c a l F

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

{c a l C C}_{> 3}

game, where

{c a l C C}_{> 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

C y c l e

game, where the players aim at avoiding all cycles.

Recommendations

Cites work

Cited in

(4)

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)