페테르센 그래프

페테르센 그래프를 두 개의 오각형으로 나타낸 그림

페테르센 그래프(Petersen graph)는 꼭지점 10개, 변 15개를 가지고 있는 그래프로, 그래프 이론의 여러 가지 문제의 반례로 쓰이거나 유용한 예로 쓰이는 중요한 그래프이다. 이 그래프의 이름은 1898년에 이 그래프를 다룬 논문을 출판한 덴마크의 수학자 페테르센(Julius Petersen)을 따서 지어졌다.

성질

페테르센 그래프의 crossing number는 2이다.

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

페테르센 그래프는 $K_5$의 라인 그래프와 여 그래프 관계에 있다.

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

페테르센 그래프는 해밀톤 경로를 가지고 있지만, 해밀톤 회로는 가지고 있지 않다.

페테르센 그래프의 crossing number는 2이다.

일반화된 페테르센 그래프

도널드 콕세터는 1950년 페테르센 그래프의 일반화된 그래프를 도입했다. 일반화된 페테르센 그래프 $G(n,k)$는 다음과 같이 정의된다.

• 그래프의 꼭지점은 $\{u_0, u_1, \cdots, u_{n-1}, v_0, v_1, \cdots, v_{n-1}\}$로 구성된다.
• 그래프의 변은 $\{u_i u_{i+1}, u_i v_i, v_i v_{i+k} | i = 0, 1, \cdots, n-1\}$로 구성된다.

이때 각 기호의 첨자가 $n-1$을 넘어가는 경우 $a_{n+i} = a_i$로 간주한다. 페테르센 그래프 자체는 $G(5, 2)$로 표기할 수 있다.