Publisher DOI: 10.1007/978-3-030-83823-2_62
Title: Waiter-Client Games on Randomly Perturbed Graphs
Language: English
Authors: Clemens, Dennis  
Hamann, Fabian  
Mogge, Yannick 
Parczyk, Olaf 
Keywords: Connectivity; Hamilton cycles; Randomly perturbed graphs; Waiter-Client games
Issue Date: 2021
Source: Trends in Mathematics 14: 397-403 (2021)
Abstract (english): 
Waiter-Client games are played on a hypergraph (X, F), where F⊆ 2X denotes the family of winning sets. During each round, Waiter offers a predefined amount (called bias) of elements from the board X, from which Client takes one for himself while the rest go to Waiter. Waiter wins the game if she can force Client to occupy any winning set F∈ F. In this paper we consider Waiter-Client games played on randomly perturbed graphs. These graphs consist of the union of a deterministic graph Gα on n vertices with minimum degree at least αn and the binomial random graph Gn,p. Depending on the bias we determine the order of the threshold probability for winning the Hamiltonicity game and the k-connectivity game on Gα∪ Gn,p.
ISSN: 2297-0215
Institute: Mathematik E-10 
Document Type: Article
Part of Series: Trends in Mathematics 
Volume number: 14
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 6, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.