Cleaning regular graphs with brushes

Noga Alon, Paweł Prałat, Nicholas Wormald

Research output: Contribution to journalArticle

25 Scopus citations

Abstract

A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most n(d + 1)/4 brushes suffice and prove that, for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely n/4(d+o(d)), thus solving a problem raised in [M.E. Messinger, R.J. Nowakowski, P. Prałat, and N. Wormald, Cleaning random d-regular graphs with brushes using a degree-greedy algorithm, in Combinatorial and Algorithmic Aspects of Networking, Lecture Notes in Comput. Sci. 4852, Springer, Berlin-Heidelberg, 2007, pp. 13-26].

Original languageEnglish (US)
Pages (from-to)233-250
Number of pages18
JournalSIAM Journal on Discrete Mathematics
Volume23
Issue number1
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Keywords

  • Cleaning process
  • Degree-greedy algorithm
  • Differential equations method
  • Random d-regular graphs

Fingerprint Dive into the research topics of 'Cleaning regular graphs with brushes'. Together they form a unique fingerprint.

  • Cite this