The purpose of the thesis is to describe and explain results on the number of Hamiltonian cycles in a graph. After describing several ways to calculate the number of Hamiltonian cycles in given graphs, we focus on the properties a uniquely Hamiltonian graph must have. Then applications of a second Hamiltonian cycle to chords in longest cycles and to chromatic polynomials are shown.
The purpose of the thesis is to describe and explain results on the number of Hamiltonian cycles in a graph. After describing several ways to calculate the number of Hamiltonian cycles in given graphs, we focus on the properties a uniquely Hamiltonian graph must have. Then applications of a second Hamiltonian cycle to chords in longest cycles and to chromatic polynomials are shown.
아무렇게나 잡은 그래프에서 해밀턴 회로의 개수를 정확하게 세는 문제는 계산 이론에서 가장 어려운 문제로 분류하는 NP 완전 문제 중의 하나이다. 하지만 특정한 종류의 그래프들만 생각한다면 해밀턴 회로의 개수를 정확히 구하거나 최소한 몇 개가 있다는 사실을 알아낼 수 있다. 서론인 제 1장을 지나 제 2장에서는 그린버그의 결과를 이용하여 확장된 페테르센 그래프가 몇 개의 해밀턴 회로를 갖는지 정확히 구하고, 이분 그래프가 최소한 몇 개의 해밀턴 회로를 갖는지 알아내는 방법을 소개한다.
3장부터 5장까지는 많은 해밀턴 회로가 어떤 의미를 가지는지에 대해서 설명한다. 해밀턴 회로가 많이 있는 그래프가 꼭 가지게 되는 성질들이 몇 가지 있는데, 재미있는 것은 그 중 일부가 단 두 개의 해밀턴 회로만 있어도 나타나게 된다는 것이다. 때문에 3장에서는 꼭 한 개의 해밀턴 회로를 갖는 그래프가 어떤 모양인지를 토마손의 결과와 로바스의 보조정리, 그리고 독립-지배 정리라고 이름 붙은 토마센의 정리를 이용해서 분류한다.
4장에서는 다시 독립-지배 정리를 이용하여 많은 수의 그래프, 정확하게는 연결도가 3 이상인 3-정규 그래프의 가장 긴 회로는 항상 현을 갖는다는 것을 증명하고, 연결도가 2인 그래프들에 대해 비슷한 결과를 얻을 수 있는 가능성을 제시한다.
5장은 해밀턴 회로가 가질 수 있는 또 다른 가능성을 이야기하는 장이다. 그래프 색칠 문제는 몇 가지 색이 주어졌을 때 그래프의 점들을 이 색깔들로 칠하되 서로 연결된 점들이 다른 색을 갖도록 만들 수 있겠냐는 문제로, 4가지 색만 있으면 지도의 서로 다른 영역들을 붙어있는 곳이 항상 다른 색깔로 표시되도록 칠할 수 있다는 4색 문제가 그래프 색칠 문제 중 가장 유명하다. 그래프 색칠 문제를 조금 더 넓게 봐서 가능한 색칠의 개수를 생각하면 이 개수가 그래프마다 고유한 다항식으로 나타난다는 사실을 보일 수 있다. 이 색깔 다항식의 근이 1보다 작거나 최소한 32/27이라는 신기한 사실을 잭슨이 증명한 이후에 토마센은 해밀턴 회로를 갖는 그래프는 색깔 다항식의 근이 최소 2가 될 것이라는 추측을 하였고, 5장에서는 이 내용들을 자세히 설명하고 토마센의 추측보다 조금 약한 결과, 자세하게 설명하면 해밀턴 경로를 갖는 그래프에 대해 32/27보다 조금 큰 수로 바꿀 수 있다는 결과를 증명한다.
