Game brush number

DOI10.1016/J.DAM.2016.02.011zbMATH Open1337.05078arXiv1412.2034OpenAlexW1585664102MaRDI QIDQ290091FDOQ290091

Authors: William B. Kinnersley, Paweł Prałat 

Publication date: 1 June 2016

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

Abstract: We study a two-person game based on the well-studied brushing process on graphs. Players Min and Max alternately place brushes on the vertices of a graph. When a vertex accumulates at least as many brushes as its degree, it sends one brush to each neighbor and is removed from the graph; this may in turn induce the removal of other vertices. The game ends once all vertices have been removed. Min seeks to minimize the number of brushes played during the game, while Max seeks to maximize it. When both players play optimally, the length of the game is the game brush number of the graph $G$, denoted $b_g(G)$. By considering strategies for both players and modelling the evolution of the game with differential equations, we provide an asymptotic value for the game brush number of the complete graph; namely, we show that $b_g(K_n)=(1+o(1))n^2/e$. Using a fractional version of the game, we couple the game brush numbers of complete graphs and the binomial random graph $mathcalG(n,p)$. It is shown that for $pngglnn$ asymptotically almost surely $b_g(mathcalG(n,p))=(1+o(1))p{b}_g(K_n)=(1+o(1))p{n}^2/e$. Finally, we study the relationship between the game brush number and the (original) brush number.

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

Recommendations

• Cleaning random graphs with brushes
• Cleaning with brooms
• Cleaning regular graphs with brushes
• Brushing with additional cleaning restrictions
• Cleaning a network with brushes

zbMATH Keywords

random graphsbrush numbercleaning process

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Title not available (Why is that?)
• Chip-firing games on graphs
• Domination game and an imagination strategy
• The chip-firing game
• A bound for the game chromatic number of graphs
• \textsc{polish} -- Let us play the cleaning game
• Game matching number of graphs
• Brushing without capacity restrictions
• Brushing with additional cleaning restrictions
• Imbalance is fixed parameter tractable
• Cleaning random graphs with brushes
• Toppling numbers of complete and random graphs
• Cleaning regular graphs with brushes
• Cleaning with brooms
• Cleaning random \(d\)-regular graphs with brooms
• Cleaning a network with brushes
• Parallel cleaning of a network with brushes
• Clean the graph before you draw it!

Cited In (2)

• Brushing number and zero-forcing number of graphs and their line graphs
• Domination game: a proof of the 3/5-conjecture for graphs with minimum degree at least two

This page was built for publication: Game brush number

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