Disjoint Connected Dominating Sets in Pseudorandom Graphs

A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure of its connectivity, and has various graph-theoretic and algorithmic implications. We show that d-regular (weakly) pseudoreandom graphs contain (1 + o(1))d/ ln d disjoint CDSs, which is asymptotically best possible. In particular, this implies that random d-regular graphs typically contain (1 + o(1))d/ ln d disjoint CDSs.