휠 그래프

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

휠 그래프
휠 그래프의 일부 예시
꼭짓점	n
모서리	2(n − 1)
지름	n>4일 때는 2 n=4일 때는 1
안둘레	3
색칠수	n이 홀수일 때는 3 n이 짝수일 때는 4
스펙트럼	${\displaystyle \{2\cos(2k\pi /(n-1))^{1};}$ ${\displaystyle k=1,\ldots ,n-2\}}$${\displaystyle \cup \{1\pm {\sqrt {n}}\}}$
특성	해밀턴 자기쌍대 평면
표기법	Wn

박보겸

ae=4

조건제시 구성

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

특성

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

휠 그래프에는 항상 해밀턴 순환이 있고 W_n에는 ${\displaystyle n^{2}-3n+3}$개의 경로가 있다(OEIS의 수열 A002061).

휠 그래프 W4의 순환 7개.

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

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

${\displaystyle P_{W_{n}}(x)=x((x-2)^{(n-1)}-(-1)^{n}(x-2)).}$

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

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