支配集

对于一个 图 和一个 顶点集 的子集 ，用 表示 中顶点集合，这些顶点在 中或与 中的顶点相邻。如果 ，那么 被称为支配集（ 中的顶点）。

最小尺寸的支配集称为最小支配集，其大小称为支配数。不是任何其他支配集的真子集的支配集称为极小支配集。

例如，在上面所示的Petersen 图中，集合 是一个支配集（实际上，是一个最小支配集）。

支配多项式编码各种大小的支配集的数量。

可以定义常见支配集的其他变体，包括所谓的全支配集。

如果一个集合是支配的且无冗余的，那么它是极大无冗余的和极小支配的 (Mynhardt and Roux 2020)。

一个支配集是极小支配的 当且仅当 它是无冗余的 (Mynhardt and Roux 2020)。

可以使用 Wolfram 语言 获取许多命名图的预计算支配集GraphData[graph,"DominatingSets"].