Disjoint connected dominating sets in pseudorandom graphs

Nemanja Draganić ( University of Oxford )

A connected dominating set (CDS) is a set of vertices that both dominates the graph and induces a connected subgraph. The number of disjoint CDSs a graph can contain serves as a natural measure of its connectivity and has interesting structural and algorithmic consequences. In this talk, I’ll show that d-regular pseudorandom graphs contain (1 + o(1))d / ln d disjoint connected dominating sets, matching the best possible asymptotic bound. This result, in particular, implies that random d-regular graphs typically achieve this optimal number. Along the way, I’ll discuss key methods from the intersection of combinatorics and theoretical computer science that apply to routing and related problems in expander graphs.