Minimum independent dominating sets of random cubic graphs

We present a heuristic for finding a small independent dominating set D of cubic graphs. We analyze the performance of this heuristic, which is a random greedy algorithm, on random cubic graphs using differential equations, and obtain an upper bound on the expected size of D. A corresponding lower bound is derived by means of a direct expectation argument. We prove that 26 asymptotically almost surely satisfies 0.2641n less than or equal to \D\ less than or equal to 0.27942n. (C) 2002 Wiley Periodicals, Inc.