질식 그래프
Strangulated graph
그래프 이론 수학에서, 질식 그래프는 3보다 큰 길이의 유도 사이클의 가장자리를 삭제하면 나머지 그래프가 분리되는 그래프다.즉, 그것들은 모든 주변 주기가 삼각형인 그래프들이다.
예
최대 평면 그래프에서, 또는 더 일반적으로 모든 다면 그래프에서 말초 주기는 그래프의 평면 내장 면이기 때문에, 모든 면이 삼각형인 경우와 동등하게 최대 평면인 경우에만 다면 그래프가 목을 조른다.코드 그래프의 유일한 유도 주기는 삼각형이기 때문에 더 이상 삭제할 주기가 없기 때문에 모든 코드 그래프는 질식된다.
특성화
두 개의 그래프의 클릭 합은 각 그래프에서 두 개의 동일한 크기의 클릭을 함께 식별한 다음 클릭 에지를 일부 삭제하여 형성된다.질식된 그래프와 관련된 클릭섬 버전의 경우 에지 삭제 단계가 생략된다.두 개의 질식 그래프 사이에 이러한 유형의 합은 다른 질식 그래프를 생성하는데, 합계의 긴 유도 사이클마다 한 쪽 또는 다른 쪽으로 제한되어야 한다(그렇지 않으면 합계의 한 쪽에서 다른 쪽으로 교차하는 정점과 삭제에 의해 형성된 해당 쪽의 연결이 끊어진 부분 사이에 화음을 가질 것이다).ng clique-sum에서 사이클이 단절된 상태로 유지되어야 한다.모든 화음 그래프는 이러한 방식으로 완전한 그래프의 집합으로 분해될 수 있으며, 모든 최대 평면 그래프는 4Vertex로 연결된 최대 평면 그래프의 집합으로 분해될 수 있다.
시모어&위버(1984)가 보여주듯이, 이러한 그래프들은 교살된 그래프의 유일한 구성 요소들이다. 교살된 그래프는 정확히 완전한 그래프와 최대 평면 그래프의 집단으로 형성될 수 있는 그래프들이다.
참고 항목
참조
- Seymour, P. D.; Weaver, R. W. (1984), "A generalization of chordal graphs", Journal of Graph Theory, 8 (2): 241–251, doi:10.1002/jgt.3190080206, MR 0742878.
