바넷 추측

바넷의 추측은 그래프의 해밀턴 사이클에 관한 수학의 한 분야인 그래프 이론의 해결되지 않은 문제입니다. 이 그래프는 캘리포니아 대학교 데이비스의 명예 교수인 데이비드 W. 바넷의 이름을 따서 지어졌습니다. 이 그래프는 꼭짓점당 3개의 간선을 가진 모든 이분 다면체 그래프는 해밀턴 사이클을 가지고 있다고 말합니다.

정의들

평면 그래프는 교차 없이 유클리드 평면에 포함될 수 있는 무방향 그래프입니다. 평면 그래프가 3-정점으로 연결된 경우에만 다면체라고 합니다. 즉, 두 개의 정점이 존재하지 않는 경우 제거하면 나머지 그래프의 연결이 끊어집니다. 그래프의 꼭짓점을 두 개의 다른 색으로 칠할 수 있는 경우 각 모서리에 각 색의 끝점이 하나씩 있을 수 있습니다. 각 꼭짓점이 정확히 3개의 간선으로 이루어진 끝점인 경우 그래프는 입방정수(또는 3-정규)입니다. 마지막으로 그래프는 각 정점을 한 번씩만 통과하는 사이클이 존재할 경우 해밀턴입니다. 바넷의 추측은 모든 입방정사 다면체 그래프가 해밀턴 그래프라는 것을 의미합니다.

슈타이니츠 정리에 따르면 평면 그래프는 볼록 다면체가 다면체인 경우에만 볼록 다면체의 모서리와 꼭짓점을 나타냅니다. 3차원 다면체는 단순 다면체일 경우에만 입방 그래프를 갖습니다. 그리고 평면 그래프는 그래프의 평면 임베딩에서 모든 면 사이클이 짝수 길이를 갖는 경우에만 이분형입니다. 따라서 바넷의 추측은 동등한 형태로 언급될 수 있습니다: 3차원 단순 볼록 다면체가 각 면에 짝수 개의 모서리를 가지고 있다고 가정하자. 그러면 추측에 의하면 다면체의 그래프는 해밀턴 사이클을 갖습니다.

역사

P. G. Tait(1884)은 모든 입방 다면체 그래프가 해밀턴 그래프라고 추측했고, 이것은 Tait의 추측으로 알려지게 되었습니다. 이는 W. T. Tutte(1946)에 의해 반증되었는데, 그는 46개의 꼭짓점으로 반증례를 만들었으며, 다른 연구자들은 나중에 더 작은 반증례를 발견했습니다. 그러나 이러한 알려진 반례들 중 어느 것도 이분법적이지 않습니다. Tutte 자신은 모든 3차 연결 이분 그래프가 해밀턴 그래프라고 추측했지만, 이는 반례인 Horton 그래프의 발견으로 거짓임이 밝혀졌습니다.^[1] 데이비드 W. 바넷(David W. Barnette, 1969)은 모든 이분입방 다면체는 해밀턴이거나, 동등하게, 모든 반례는 이분입방체가 아니라고 말하면서, Tait와 Tutte의 추측의 약화된 조합을 제안했습니다.

동등양식

켈만스([2]Kelmans, 1994)는 바넷의 추측이 표면적으로 더 강한 진술과 동등하다는 것을 보여주었고, 이는 이분입방 다면체의 동일한 면에 있는 모든 두 모서리 e와 f에 대해 e는 포함하지만 f는 포함하지 않는 해밀턴 사이클이 존재한다는 것을 보여주었습니다. 분명히 이 문장이 사실이라면, 모든 이분입방 다면체는 임의로 e와 f를 선택하는 해밀턴 사이클을 포함합니다. 다른 방향으로 켈만스는 반례가 원래 바넷 추측의 반례로 변형될 수 있음을 보여주었습니다.

바넷의 추측은 또한 모든 입방 이분 다면체 그래프의 이중 꼭짓점이 유도된 부분 그래프가 트리인 두 부분 집합으로 분할될 수 있다는 진술과 동일합니다. 이중 그래프에서 이러한 분할에 의해 유도된 절단은 기본 그래프에서 해밀턴 사이클에 해당합니다.^[3]

부분결과

Barnette의 추측의 진실은 여전히 알려지지 않았지만, 계산 실험은 86개 이하의 정점을 가진 반례가 없다는 것을 보여주었습니다.^[4]

Barnette의 추측이 거짓으로 판명되면, 이분입방 다면체가 해밀턴인지 여부를 테스트하기 위해 NP-완전한 것으로 나타날 수 있습니다.^[5] 평면 그래프가 이분형이고 입방형이지만 연결도 2만인 경우, 비 해밀턴형일 수 있으며, 이러한 그래프에 대해 해밀턴성을 테스트하는 것은 NP-완전입니다.^[6] Alt et al. (2016)에 의해 또 다른 결과가 얻어졌습니다. 만약 듀얼 그래프가 파란색, 빨간색 및 녹색으로 꼭지점 색상을 지정하여 모든 적색-녹색 사이클이 4도의 꼭지점을 포함할 수 있다면, 기본 그래프는 해밀턴 그래프입니다.

관련문제

바넷의 관련 추측은 모든 면이 6개 이하의 간선을 갖는 모든 입방 다면체 그래프는 해밀턴 그래프라고 말합니다. 계산 실험 결과, 만약 어떤 반례가 존재한다면, 그것은 177개 이상의 꼭짓점을 가져야 한다는 것을 보여주었습니다.^[7] 이 추측은 Kardosh(2020)에 의해 증명되었습니다.

이 두 추측의 교차점은 모든 면이 4개 또는 6개의 간선을 갖는 모든 이분입방 다면체 그래프가 해밀턴이라는 것입니다. 이것은 Goodey (1975)에 의해 사실로 증명되었습니다.

메모들

참고문헌

• Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs", Journal of Information Processing, 3 (2): 73–76, MR 0596313
• Alt, Helmut; Payne, Michael S.; Schmidt, Jens M.; Wood, David R. (2016), "Thoughts on Barnette's conjecture" (PDF), Australasian Journal of Combinatorics, 64 (2): 354–365, MR 3442496
• Aldred, R. E. L.; Bau, S.; Holton, D. A.; McKay, Brendan D. (2000), "Nonhamiltonian 3-connected cubic planar graphs", SIAM Journal on Discrete Mathematics, 13 (1): 25–32, doi:10.1137/S0895480198348665, MR 1737931
• Barnette, David W. (1969), "Conjecture 5", in Tutte, W. T. (ed.), Recent Progress in Combinatorics: Proceedings of the Third Waterloo Conference on Combinatorics, May 1968, New York: Academic Press, MR 0250896
• Feder, Tomas; Subi, Carlos (2006), On Barnette's conjecture, ECCC TR06-015
• Florek, Jan (2010), "On Barnette's conjecture", Discrete Mathematics, 310 (10–11): 1531–1535, doi:10.1016/j.disc.2010.01.018, MR 2601261
• Goodey, P. R. (1975), "Hamiltonian circuits in polytopes with even sided faces", Israel Journal of Mathematics, 22 (1): 52–56, doi:10.1007/BF02757273, MR 0410565
• Hertel, Alexander (2005), A survey & strengthening of Barnette's conjecture (PDF)
• Holton, D. A.; Manvel, B.; McKay, B. D. (1985), "Hamiltonian cycles in cubic 3-connected bipartite planar graphs", Journal of Combinatorial Theory, Series B, 38 (3): 279–297, doi:10.1016/0095-8956(85)90072-3, MR 0796604
• Horton, J. D. (1982), "On two-factors of bipartite regular graphs", Discrete Mathematics, 41 (1): 35–41, doi:10.1016/0012-365X(82)90079-6, MR 0676860
• Kardoš, F. (2020), "A computer-assisted proof of the Barnette-Goodey Conjecture: not only fullerene graphs are hamiltonian", SIAM Journal on Discrete Mathematics, 34 (1): 62–100, arXiv:1409.2440, doi:10.1137/140984737, S2CID 119660011
• Kelmans, A. K. (1994), "Constructions of cubic bipartite 3-connected graphs without Hamiltonian cycles", in Kelmans, A. K. (ed.), Selected Topics in Discrete Mathematics: Proceedings of the Moscow Discrete Mathematics Seminar 1972–1990, American Mathematical Society Translations, Series 2, vol. 158, pp. 127–140
• Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46과학논문에 Tait, P. G. (1884), "Listing's Topologie", Philosophical Magazine, 5th Series, 17: 30–46재인쇄, 제1권. II, pp. 85–98
• Tutte, W. T. (1946), "On Hamiltonian circuits", Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112/jlms/s1-21.2.98
• Tutte, W. T. (1971), "On the 2-factors of bicubic graphs", Discrete Mathematics, 1 (2): 203–208, doi:10.1016/0012-365X(71)90027-6, MR 0291010

외부 링크

• Weisstein, Eric W., "Barnette's Conjecture", MathWorld
• 열린 문제 정원에서의 바넷의 추측, 로버트 사말, 2007.