支配數

圖 的 支配劃分 中不相交的 支配集 的最大數量稱為其支配數 。

支配數不應與支配數混淆，後者是最小的單個支配集的大小。

設 為圖 的最小頂點度，則

因此，具有一個或多個孤立點的圖的支配數為 1。

此外，如果已知圖 的支配數 ，則

其中 表示 的頂點數，而 是向下取整函式。

找到圖的支配數在計算上是困難的。

給定一個完整的極小支配集集合，圖 的支配數可以被找到，作為頂點是 的極小支配集，且邊存在於具有非空交集的集合對之間的圖的獨立數。