정규 그래프

정규 그래프(定規graph, 틀:Llang)는 모든 꼭짓점이 동일한 수의 이웃을 가지는 그래프이다. 즉, 모든 꼭짓점이 같은 차수를 가진다.

정의

자연수 $k \in ℕ$ 가 주어졌다고 하자. 만약 어떤 그래프에서 모든 꼭짓점의 차수(꼭짓점에 잇닿은 변의 수)가 $k$ 라면, 이 그래프를 $k$ -정규 그래프( $k$ -定規graph, 틀:Llang)라고 한다.

3-정규 그래프는 삼차 그래프(三次graph, 틀:Llang)라고도 한다.

내시윌리엄스 정리(틀:Llang)에 따르면, $2 k + 1$ 개의 꼭짓점을 갖는 $k$ -정규 그래프는 항상 해밀턴 순환을 갖는다.

3-정규 그래프의 최소 교차점 개수(틀:Llang)를 찾는 문제는 NP-난해이다.^[1]

두 자연수 $n, k \in ℕ$ 이 주어졌을 때, 다음 두 조건이 서로 동치이다.

0-정규 그래프는 무변 그래프이다. 1-정규 그래프의 연결 성분은 경로 그래프 $K_{2} = P_{2}$ 이다. 2-정규 그래프의 연결 성분은 순환 그래프나 무한 경로 그래프이다.

$n$ 개의 꼭짓점의 완전 그래프 $K_{n}$ 은 $n - 1$ -정규 그래프이다.

1880년에 피터 거스리 테이트는 모든 삼차 그래프는 해밀턴 경로를 가진다는 추측을 내놓았지만, 1946년에 윌리엄 토머스 텃이 46개 꼭짓점을 가진 반례를 찾았다.

1971년에 윌리엄 토머스 텃은 모든 이분 삼차 그래프는 해밀턴 회로가 있을 것이라고 추측했지만, 조지프 호턴(틀:Llang)이 96개 꼭짓점을 가진 반례를 찾아냈다.

모든 이분 삼차 그래프가 해밀턴 회로가 짝수개 존재한다는 것은 증명되어 있다.

내시윌리엄스 정리는 영국의 수학자 크리스핀 내시윌리엄스(틀:Llang)가 증명하였다.