Game brush number

DOI10.1016/J.DAM.2016.02.011MaRDI QIDQ290091zbMATHOpenAlexFDO

Authors William B. Kinnersley, Paweł Prałat

Publication date 1 June 2016

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

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

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)

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.

Recommendations

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

Cites work

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

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)