Random Procedures for Dominating Sets in Graphs

  • Sarah Artmann
  • Frank Göring
  • Jochen Harant
  • Dieter Rautenbach
  • Ingo Schiermeyer

Abstract

We present and analyze some random procedures for the construction of small dominating sets in graphs. Several upper bounds for the domination number of a graph are derived from these procedures.

Published
2010-07-20
Article Number
R102