Random Procedures for Dominating Sets in Graphs
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.