全支配集

对于一个图 和顶点集 的一个子集 ，记 为图 中与子集 中的一个顶点相邻的顶点集合。如果 ，则 被称为（图 中的顶点的）全支配集。因为全支配集的成员必须与另一个顶点相邻，所以全支配集未定义于具有孤立顶点的图中。

全支配集与普通的支配集不同之处在于，在全支配集 中， 的成员本身需要与 中的一个顶点相邻，而对于一个普通的支配集 ， 的成员可以是在 本身中，或者与 中的顶点相邻。

例如，在上面图示的 Petersen 图 中，集合 是一个（最小）支配集（左图），而 是一个（最小）全支配集（右图）。

最小全支配集的大小 被称为全支配数。