Random Procedures for Dominating Sets in Graphs

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


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.

Full Text: PDF