그래프 이론수학 분야에서, 휠 그래프는 한 꼭짓점이 순환 그래프의 모든 꼭짓점에 연결해서 생긴 것이다. 꼭짓점이 n개인 휠 그래프는 (n-1)각뿔1차원 뼈대로 정의할 수 있다. 일부 사람들[1]Wn을 꼭짓점이 n개(n≥ 4) 있는 휠 그래프를 가리킬 때 쓴다; 다른 사람들[2]은 대신에 Wn를 꼭짓점이 n+1개(n ≥ 3) 있는 휠 그래프를 가리킬 때 쓴다. 이것은 한 꼭짓점을 길이가 n인 순환 그래프의 모든 꼭짓점에 연결하면서 생긴 것이다. 이 문서의 나머지는 앞의 표기법을 사용한다.

휠 그래프
휠 그래프의 일부 예시
꼭짓점n
모서리2(n − 1)
지름n>4일 때는 2
n=4일 때는 1
안둘레3
색칠수n이 홀수일 때는 3
n이 짝수일 때는 4
스펙트럼
특성해밀턴
자기쌍대
평면
표기법Wn

조건제시 구성 편집

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

특성 편집

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

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

 
휠 그래프 W4의 순환 7개.

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

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

 

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

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

각주 편집

  1. Weisstein, Eric Wolfgang. “Wheel Graph”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
  2. Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications, 7th ed., McGraw-Hill, p. 655.
  3. Trudeau, Richard J. (1993). 《Introduction to Graph Theory》 Correct, enlarg republication.판. New York: Dover Pub. 56쪽. ISBN 978-0-486-67870-2. 2012년 8월 8일에 확인함. 
  4. Buckley, Fred; Harary, Frank (1988), “On the euclidean dimension of a wheel”, 《Graphs and Combinatorics4 (1): 23–30, doi:10.1007/BF01864150 .
  5. Faudree, Ralph J.; McKay, Brendan D. (1993), “A conjecture of Erdős and the Ramsey number r(W6)”, 《J. Combinatorial Math. and Combinatorial Comput.》 13: 23–31 .

외부 링크 편집

  •   위키미디어 공용에 휠 그래프 관련 미디어 분류가 있습니다.