페테르센 그래프

페테르센 그래프

페테르센 그래프의 교차수(영어: crossing number)는 2이다.

그래프 이론에서, 페테르센 그래프(영어: Petersen graph)는 꼭짓점 10개, 변 15개를 가지고 있는 그래프이다. 여러 가지 추측들의 반례로 쓰인다.

정의

일반화 페테르센 그래프(영어: generalized Petersen graph) $G(n,k)$$G(n,k)$는 다음과 같은 그래프이다.

$V(G(n,k))=\{u_{i},v_{i}\colon i\in \mathbb {Z} /n\}$$V(G(n,k))=\{u_{i},v_{i}\colon i\in {\mathbb Z}/n\}$

$E(G(n,k))=\{u_{i}u_{i+1},u_{i}v_{i},v_{i}v_{i+k}\colon i\in \mathbb {Z} /n\}$$E(G(n,k))=\{u_{i}u_{{i+1}},u_{i}v_{i},v_{i}v_{{i+k}}\colon i\in {\mathbb Z}/n\}$

여기서 첨자는 법 $n$$n$으로 계산한다. 즉, $u_{n+i}=u_{i}$$u_{{n+i}}=u_{i}$ 및 $v_{n+i}=u_{i}$$v_{{n+i}}=u_{i}$로 간주한다.

페테르센 그래프는 일반화 페테르센 그래프 $G(5,2)$$G(5,2)$이다.

성질

페테르센 그래프는 평면 그래프가 아니며, 완전 그래프 $K_{5}$$K_{5}$와 완전 이분 그래프 $K_{3,3}$$K_{{3,3}}$를 마이너로 가진다.

페테르센 그래프는 $K_{5}$$K_{5}$의 선 그래프의 여 그래프와 동형이다.

페테르센 그래프는 3가지 색으로 변을 칠할 수 없는 제일 작은 삼차 그래프이다.

페테르센 그래프는 해밀턴 경로를 가지고 있지만, 해밀턴 순환을 가지고 있지 않다.

페테르센 그래프의 교차수(영어: crossing number)는 2이다.

역사

1898년에 덴마크의 수학자 율리우스 페테르센(덴마크어: Julius Petersen)이 이 그래프를 다룬 논문을 출판하였으며, 이로부터 명명되었다.

해럴드 스콧 맥도널드 콕서터는 1950년에 일반화 페테르센 그래프를 도입하였다.

참고 문헌

• Holton, D. A.; J. Sheehan (1993). 《The Petersen graph》. Cambridge University Press. doi:10.2277/0521435943. ISBN 0-521-43594-3. 

바깥 고리

• “Petersen graph”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Eric Wolfgang Weisstein. “Petersen graph”. 《Wolfram MathWorld》 (영어). Wolfram Research.