## Abstract

A dominating set script D sign of a graph G is a subset of V(G) such that, for every vertex v ∈ V(G), either in v ∈ script D sign or there exists a vertex u ∈ script D sign that is adjacent to v. We are interested in finding dominating sets of small cardinality. A dominating set ℒ of a graph G is said to be independent if no two vertices of ℒ are connected by an edge of G. The size of a smallest independent dominating set of a graph G is the independent domination number of G. 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.

Original language | English |
---|---|

Pages (from-to) | 513-522 |

Number of pages | 10 |

Journal | Combinatorics, Probability and Computing |

Volume | 15 |

Issue number | 4 |

DOIs | |

Publication status | Published - Jul 2006 |

Externally published | Yes |