On the Independent Domination Number of Random Regular Graphs

Abstract

A dominating set $\cal D$ of a graph $G$ is a subset of $V(G)$ such that, for every vertex $v\in V(G)$, either in $v\in {\cal D}$ or there exists a vertex $u \in {\cal D}$ that is adjacent to $v$. We are interested in finding dominating sets of small cardinality. A dominating set $\cal I$ of a graph $G$ is said to be independent if no two vertices of ${\cal I}$ 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.