连通支配集

在连通图 中的连通支配集是 中的一个支配集，其顶点导出连通子图，即其中没有不与某个其他支配顶点通过边连接的支配顶点。因此，连通支配集构成图中所有支配集的子集。

图 的最小连通支配集是尺寸尽可能小的连通支配集，其中最小尺寸表示为 ，称为连通支配数。