On the independent domination number of random regular graphs

W. Duckworth, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

18 Citations (Scopus)

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 languageEnglish
Pages (from-to)513-522
Number of pages10
JournalCombinatorics Probability and Computing
Volume15
Issue number4
DOIs
Publication statusPublished - Jul 2006
Externally publishedYes

Cite this