Bounds for the competition-independence game on trees

DOI10.1016/J.DISC.2023.113827arXiv2303.09993MaRDI QIDQ6177429FDOQ6177429

Authors: Jan Petr, Julien Portier 

Publication date: 17 January 2024

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

Abstract: In this paper we prove that Sweller has a strategy so that the Sweller-Start Competition-Independence game lasts at least $(5n+3)/13$ moves for every tree. Moreover, we show that there exist arbitrarily large trees such that the Sweller-Start Competition-Independence game lasts at most $(5n+26)/12$ moves, disproving a conjecture by Henning.

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

Recommendations

• The competition-independence game in trees
• scientific article; zbMATH DE number 1933246
• Domination game played on trees and spanning subgraphs
• Building spanning trees quickly in maker-breaker games
• Building spanning trees quickly in maker-breaker games

zbMATH Keywords

treesgames on graphsindependent setscompetition-independence game

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Mathematical programming (90Cxx)

Cites Work

• Domination game and an imagination strategy
• Extremal problems for game domination number
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two
• Title not available (Why is that?)
• Domination games played on graphs
• Transversal game on hypergraphs and the \(\frac{3}{4}\)-conjecture on the total domination game
• Game domination number
• The 4/5 upper bound on the game total domination number
• My favorite domination game conjectures
• The competition-independence game in trees

This page was built for publication: Bounds for the competition-independence game on trees

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