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.

Authors

• Nemanja Draganic
• Michael Krivelevich

Keywords

• Connected dominating set (CDS)
• connectivity
• pseudorandom graphs