

























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。