휠 그래프

박보겸 ae=4그래프 이론의 수학 분야에서, 휠 그래프는 한 꼭짓점이 순환 그래프의 모든 꼭짓점에 연결해서 생긴 것이다. 꼭짓점이 n개인 휠 그래프는 (n-1)각뿔의 1차원 뼈대로 정의할 수 있다. 일부 사람들은 Wn을 꼭짓점이 n개(n≥ 4) 있는 휠 그래프를 가리킬 때 쓴다; 다른 사람들Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, p. 655.은 대신에 Wn를 꼭짓점이 n+1개(n ≥ 3) 있는 휠 그래프를 가리킬 때 쓴다. 이것은 한 꼭짓점을 길이가 n인 순환 그래프의 모든 꼭짓점에 연결하면서 생긴 것이다. 이 문서의 나머지는 앞의 표기법을 사용한다.

조건제시 구성
꼭짓점의 집합 {1,2,3,…,v}이 주어졌을 때, 휠 그래프의 모서리의 집합은 조건제시법에서 {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}로 표현할 수 있다.

특성
휠 그래프는 평면 그래프이므로 유일한 평면 매립이 있다. 더 구체적으로, 모든 휠 그래프는 할린 그래프이다. 이것은 자기쌍대이다: 어떤 휠 그래프의 평면 쌍대는 동형 그래프이다. K4 = W4를 제외한 모든 최대 평면 그래프는 부분 그래프로 W5나 W6를 가진다.

휠 그래프에는 항상 해밀턴 순환이 있고 Wn에는 개의 경로가 있다.

320px휠 그래프 W4의 순환 7개.

n이 홀수일 때, Wn은 색칠수가 3인 완벽 그래프이다: 순환의 꼭짓점은 두 색으로 주어질 수 있고, 중심의 꼭짓점은 세 번째 색이 주어진다. n이 짝수일 때, Wn은 색칠수가 4이고, (n ≥ 6일 때) 완벽하지 않다.  W7은 유클리드 평면에서 단위 거리 그래프인 유일한 휠 그래프이다..

휠 그래프 Wn의 색칠 다항식은:

매트로이드 이론에서, 매트로이드의 특히 중요한 두 특수 클래스는 휠 매트로이드와 whirl 매트로이드으로 둘 다 휠 그래프에서 파생된 것이다. k-휠 매트로이드는 휠 그래프 Wk+1의 그래픽 매트로이드이고, k-whirl 매트로이드는 k-휠 매트로이드에서 휠 그래프의 외부 순환과 그 신장 부분 그래프를 독립적으로 생각해서 파생된 것이다.

휠 W6은 램지 이론에서 에르되시 팔의 추측의 반례를 제공한다: 그의 추측은 완전 그래프는 같은 색칠 수를 가지는 중에서 가장 작은 램지 수를 가진다는 것이나, Faudree와 McKay (1993)는 K4가 램지 수 18을 가지는 반면 같은 색칠수를 가지는 W6가 램지 수 17을 가진다는 것을 보였다.. 즉, 꼭짓점이 17개인 모든 그래프 G에 대해서, G나 그 여 그래프가 부분 그래프로 W6을 가지고 있으나, 꼭짓점이 17개인 페일리 그래프나 그 여 그래프 모두 K4를 가지고 있지 않다.

 각주 

 외부 링크 


분류:평면 그래프