On the Independent Domination Number of Random Regular Graphs
William Duckworth, N. C. Wormald · Combinatorics Probability Computing · 2006
A dominating set . In this paper we present upper bounds on the independent domination number of random regular graphs. This is achieved by analysing the performance of a randomized greedy algorithm on random regular graphs using differential equations.