A new Perspective on Vertex Connectivity

Edge connectivity and vertex connectivity are two fundamental concepts in graph theory. Although by now there is a good understanding of the structure of graphs based on their edge connectivity, our knowledge in the case of vertex connectivity is much more limited. An essential tool in capturing edge connectivity are edge-disjoint spanning trees. The famous results of Tutte and Nash-Williams show that a graph with edge connectivity $\lambda$ contains $\floor{\lambda/2}$ edge-disjoint spanning trees. We present connected dominating set (CDS) partition and packing as tools that are analogous to edge-disjoint spanning trees and that help us to better grasp the structure of graphs based on their vertex connectivity. The objective of the CDS partition problem is to partition the nodes of a graph into as many connected dominating sets as possible. The CDS packing problem is the corresponding fractional relaxation, where CDSs are allowed to overlap as long as this is compensated by assigning appropriate weights. CDS partition and CDS packing can be viewed as the counterparts of the well-studied edge-disjoint spanning trees, focusing on vertex disjointedness rather than edge disjointness. We constructively show that every $k$-vertex-connected graph with $n$ nodes has a CDS packing of size $\Omega(k/\log n)$ and a CDS partition of size $\Omega(k/\log^5 n )$. We moreover prove that the $\Omega(k/\log n)$ CDS packing bound is existentially optimal. CDS packing allows us to analyze vertex connectivity in the of context random vertex sampling. We show that if vertices of a $k$-vertex-connected graph are independently sampled with probability $p$, then the graph induced by the sampled vertices has vertex connectivity $\tilde{\Omega}(kp^2)$. This bound is optimal up to polylogarithmic factors. As an additional application, we also show that CDS packings are tightly related to the (throughput of) store-and-forward algorithms in the networking model where in each time unit, each node can send one bounded-size message to all its neighbors. As a consequence, our $\Omega(k/\log n)$ CDS packing construction yields a store-and-forward broadcast algorithm with optimal throughput.