支配数

图 的 支配划分 中不相交的 支配集 的最大数量称为其支配数 。

支配数不应与支配数混淆，后者是最小的单个支配集的大小。

设 为图 的最小顶点度，则

因此，具有一个或多个孤立点的图的支配数为 1。

此外，如果已知图 的支配数 ，则

其中 表示 的顶点数，而 是向下取整函数。

找到图的支配数在计算上是困难的。

给定一个完整的极小支配集集合，图 的支配数可以被找到，作为顶点是 的极小支配集，且边存在于具有非空交集的集合对之间的图的独立数。