한 단계 이웃을 포함한다
A—B—C라는 경로에서는 {B}가 지배 집합이다. A와 C가 모두 B와 직접 연결되어 있기 때문이다. 멀리 여러 간선을 거쳐 갈 수 있다는 것만으로 지배 조건이 충족되는 것은 아니다.
고립 정점
고립 정점은 어떤 다른 정점과도 인접하지 않으므로 지배 집합에 직접 포함해야 한다. 그래프가 분리되어 있다면 각 부분의 정점들도 빠짐없이 조건을 만족해야 한다.
정점 덮개와의 차이
정점 덮개는 모든 간선의 끝점을 하나 이상 고르는 조건이고 지배 집합은 모든 정점을 자신이나 이웃으로 포함하는 조건이다. 고립 정점은 덮을 간선이 없어 정점 덮개에 필요하지 않아도 지배 집합에는 필요하다.
최소와 극소
어떤 정점을 빼도 더는 지배하지 못하면 극소 지배 집합이다. 모든 지배 집합 중 크기가 가장 작으면 최소 지배 집합이다. 집합을 더 줄일 수 없다는 사실만으로 전역 최솟값을 구했다고 할 수는 없다.
관련 문서
정점 덮개 / 독립 집합 (그래프 이론) / 경로 그래프 / 연결 성분 / 정점 (그래프 이론) / 간선 (그래프 이론) / 무향 그래프