Hamiltonian maker-breaker games on small graphs

DOI10.1080/10586458.2019.1586599zbMATH Open1481.91039arXiv1708.07579OpenAlexW2964017029WikidataQ128050746 ScholiaQ128050746MaRDI QIDQ3383707FDOQ3383707

Authors: Miloš Stojaković, Nikola Trkulja 

Publication date: 16 December 2021

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

Abstract: We look at the unbiased Maker-Breaker Hamiltonicity game played on the edge set of a complete graph $K_n$, where Maker's goal is to claim a Hamiltonian cycle. First, we prove that, independent of who starts, Maker can win the game for $n=8$ and $n=9$. Then we use an inductive argument to show that, independent of who starts, Maker can win the game if and only if $ngeq8$. This, in particular, resolves in the affirmative the long-standing conjecture of Papaioannou. We also study two standard positional games related to Hamiltonicity game. For Hamiltonian Path game, we show that Maker can claim a Hamiltonian path if and only if $ngeq5$, independent of who starts. Next, we look at Fixed Hamiltonian Path game, where the goal of Maker is to claim a Hamiltonian path between two predetermined vertices. We prove that if Maker starts the game, he wins if and only if $ngeq7$, and if Breaker starts, Maker wins if and only if $ngeq8$. Using this result, we are able to improve the previously best upper bound on the smallest number of edges a graph on $n$ vertices can have, knowing that Maker can win the Maker-Breaker Hamiltonicity game played on its edges. To resolve the outcomes of the mentioned games on small (finite) boards, we devise algorithms for efficiently searching game trees and then obtain our results with the help of a computer.

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

Recommendations

• On two problems regarding the Hamiltonian cycle game
• Hamiltonian games
• A sharp threshold for the Hamilton cycle Maker–Breaker game
• Fast winning strategies in maker-breaker games
• A Hamiltonian game on \(K_{n,n}\)

zbMATH Keywords

game theorygames on graphspositional gamesmaker-breaker games

Mathematics Subject Classification ID

2-person games (91A05) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Combinatorial games (91A46)

Cites Work

• Practical graph isomorphism. II.
• Positional games
• The critical bias for the Hamiltonicity game is (1+𝑜(1))𝑛/ln𝑛
• Biased Positional Games
• On two problems regarding the Hamiltonian cycle game
• Title not available (Why is that?)
• Global maker-breaker games on sparse graphs
• Building spanning trees quickly in maker-breaker games
• A Hamiltonian Game

Cited In (9)

• Title not available (Why is that?)
• Maker-breaker domination game on trees when Staller wins
• On two problems regarding the Hamiltonian cycle game
• Hamiltonian games
• Fast winning strategies for staller in the maker-breaker domination game
• A Hamiltonian game on \(K_{n,n}\)
• Complexity of maker-breaker games on edge sets of graphs
• Thresholds for the monochromatic clique transversal game
• A sharp threshold for the Hamilton cycle Maker–Breaker game

This page was built for publication: Hamiltonian maker-breaker games on small graphs

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