휠 그래프

휠 그래프
휠 그래프
	휠 그래프의 몇 가지 예
꼭지점	n
가장자리	2(n-1)
직경	2 if n > 4; 1 if n = 4
둘레	3
색수	n이 짝수일 경우 4; n이 홀수일 경우 3
스펙트럼	;
특성.	해밀턴식; 셀프듀얼; 평면
표기법	Wn
	그래프 및 매개 변수 표

그래프 이론의 수학 분야에서, 휠 그래프는 하나의 보편적인 정점을 순환의 모든 정점에 연결함으로써 형성된 그래프이다.n개의 정점이 $있는$ 휠 그래프는 ( $n$ – $1$ )-곤형 피라미드의 1-스켈레톤으로도 정의할 수 있습니다.어떤^[1] 저자는 W를 n개의 정점이 있는 $바퀴$ 그래프( $n 4$ 4)를 나타내기 위해 $쓰고 n$ , 다른 저자는^[2] 대신 길이 n의 $모든$ 정점에 단일 정점을 연결하여 형성된 n + $1개$ 의 정점이 있는 $바퀴$ 그래프(n $3$ 3)를 나타내기 위해 W를 $사용$ 한다_n.이 문서의 나머지 부분에서는 앞의 표기법을 사용합니다.

세트빌더 구조

정점 집합 {1, 2, 3, …, v}이(가) 지정된 경우 휠 그래프의 가장자리 집합은 세트 빌더 표기로 {{1, 2, {1,3}, …, {1, v}, {2, 3}, {3, 4}, {v - 1, v}, {v,2}^[3]로 나타낼 수 있습니다.

특성.

휠 그래프는 평면 그래프이므로 고유한 평면 임베딩이 있습니다.구체적으로 말하면, 모든 휠 그래프는 할린 그래프입니다.이들은 자기 쌍대입니다. 휠 그래프의 평면 쌍대는 동형 그래프입니다.K = W를₄ 제외한₄ 모든 최대 평면 그래프는 하위 그래프로 W 또는₆ W를₅ 포함한다.

휠 그래프에는 항상 Hamiltonian 사이클이 있고 W에는_n $n^{2}-3n+3$ 의 $n^{2}-3n+3$ - $n^{2}-3n+3$ + 3 $(디스플레이 스타일$ n $^{2}-3n+3$ ) 사이클이 $n^{2}-3n+3$ $n^{2}-3n+3$ (OEIS의 시퀀스 A002061).

휠 그래프₄ W의 7 사이클.

n의 홀수값의 경우 W는_n 색수 3을 갖는 완벽한 그래프입니다. 사이클의 정점은 두 가지 색으로, 중앙 정점은 세 번째 색으로 지정할 수 있습니다.짝수 n에 대해 W는_n 색수 4를 가지며 (nwhen 6일 때) 완전하지 않다.W는₇ 유클리드 ^[4]평면에서 단위 거리 그래프인 유일한 휠 그래프입니다.

휠 그래프_n W의 색 다항식은 다음과 같습니다.

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

매트로이드 이론에서, 매트로이드의 두 가지 특별한 클래스는 휠 매트로이드와 소용돌이 매트로이드이며, 둘 다 휠 그래프에서 파생됩니다.k-휠 매트로이드는 바퀴_k+1 W의 그래픽 매트로이드이며, k-와일 매트로이드는 바퀴의 외부 사이클과 모든 스패닝 트리가 독립적이라고 간주하여 k-휠에서 도출된다.

바퀴 60폴 Erdős의 램지 이론에 대한 추측에:그는 완전 그래프 모든 그래프 사이의 같은 색 수와 가장 작은 램지 수가 된 것으로 추측하기도 했고, Faudree와 매케이(1993년) 같은 색 수, K4과 함께 완전 그래프 램지 수 1이 60램지 수 17다는 것을 보여 주는 반증을 공급했다.8.[5]즉, 모든 17-vertex 그래프 G에 대해 G 또는 그 보완은 하위 그래프로 W를 포함하지만₆, 17-vertex Paley 그래프와 그 보완은 모두 K의₄ 복사본을 포함하지 않는다.

레퍼런스

^ Weisstein, Eric W. "Wheel Graph". MathWorld.
^ Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 978-0073383095.
^ Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 56. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.
^ 를 클릭합니다Buckley, Fred; Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics, 4 (1): 23–30, doi:10.1007/BF01864150.
^ 를 클릭합니다Faudree, Ralph J.; McKay, Brendan D. (1993), "A conjecture of Erdős and the Ramsey number r(W₆)", J. Combinatorial Math. and Combinatorial Comput., 13: 23–31.

[1] Weisstein, Eric W. "Wheel Graph". MathWorld.

[2] Rosen, Kenneth H. (2011). Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill. p. 655. ISBN 978-0073383095.

[3] Trudeau, Richard J. (1993). Introduction to Graph Theory (Corrected, enlarged republication. ed.). New York: Dover Pub. p. 56. ISBN 978-0-486-67870-2. Retrieved 8 August 2012.

[4] 를 클릭합니다Buckley, Fred; Harary, Frank (1988), "On the euclidean dimension of a wheel", Graphs and Combinatorics, 4 (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(W₆)", J. Combinatorial Math. and Combinatorial Comput., 13: 23–31.

[1]

[2]

[3]

[4]

Search

휠 그래프

네임스페이스

더

세트빌더 구조

특성.

레퍼런스