Bounds for the competition-independence game on trees

DOI10.1016/J.DISC.2023.113827MaRDI QIDQ6177429zbMATH OpenFDO

Authors Jan Petr, Julien Portier

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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)