Гипотеза Барнетта

Нерешенная задача по математике :

Является ли каждый кубический двудольный многогранный граф гамильтоновым?

Гипотеза Барнетта — нерешенная проблема теории графов , раздела математики , касающаяся гамильтоновых циклов в графах. Он назван в честь Дэвида В. Барнетта , почетного профессора Дэвисе Калифорнийского университета в ; он утверждает, что каждый двудольный многогранный граф с тремя ребрами на вершину имеет гамильтонов цикл.

Определения

Планарный граф — это неориентированный граф , который можно вложить в евклидову плоскость без каких-либо пересечений . Плоский граф называется многогранником тогда и только тогда, когда он 3-вершинно связен , то есть если не существует двух вершин, удаление которых отключило бы остальную часть графа. Граф является двудольным , если его вершины можно раскрасить в два разных цвета так, что каждое ребро имеет по одной конечной точке каждого цвета. Граф является кубическим (или 3-регулярным ), если каждая вершина является концом ровно трех ребер. Наконец, граф является гамильтоновым , если существует цикл, проходящий через каждую его вершину ровно один раз. Гипотеза Барнетта утверждает, что каждый кубический двудольный многогранный граф является гамильтоновым.

По теореме Стейница плоский граф представляет ребра и вершины выпуклого многогранника тогда и только тогда, когда он многогранник. Трехмерный многогранник имеет кубический граф тогда и только тогда, когда он является простым многогранником . И планарный граф является двудольным тогда и только тогда, когда при планарном вложении графа все циклы граней имеют четную длину. Поэтому гипотезу Барнетта можно сформулировать в эквивалентной форме: предположим, что трехмерный простой выпуклый многогранник имеет четное число ребер на каждой из своих граней. Тогда согласно гипотезе график многогранника имеет гамильтонов цикл.

История

П. Г. Тейт ( 1884 ) предположил, что каждый граф кубических многогранников гамильтонов; это стало известно как гипотеза Тейта . Его опроверг У.Татте ( 1946 ), построивший контрпример с 46 вершинами; другие исследователи позже нашли еще меньшие контрпримеры. Однако ни один из этих известных контрпримеров не является двусторонним. Сам Тутте предположил, что каждый кубический 3-связный двудольный граф является гамильтоновым, но это было доказано открытием контрпримера, графа Хортона . ^{[ 1 ]} Дэвид В. Барнетт ( 1969 ) предложил ослабленную комбинацию гипотез Тейта и Тутта, заявив, что каждый двудольный кубический многогранник является гамильтоновым или, что то же самое, что каждый контрпример к гипотезе Тейта не является двудольным.

Эквивалентные формы

Кельманс (1994) ^{[ 2 ]} показал, что гипотеза Барнетта эквивалентна на первый взгляд более сильному утверждению, что для каждых двух ребер e и f на одной и той же грани двудольного кубического многогранника существует гамильтонов цикл, который содержит e , но не содержит f . Ясно, что если это утверждение верно, то каждый двудольный кубический многогранник содержит гамильтонов цикл: достаточно выбрать e и f произвольно. В других направлениях Кельманс показал, что контрпример может быть преобразован в контрпример к исходной гипотезе Барнетта.

Гипотеза Барнетта также эквивалентна утверждению, что вершины двойственного к каждому кубическому двудольному многогранному графу можно разделить на два подмножества, индуцированные подграфы которых являются деревьями. Разрез, индуцированный таким разбиением в двойственном графе, соответствует гамильтонову циклу в простом графе. ^{[ 3 ]}

Частичные результаты

Хотя истинность гипотезы Барнетта остается неизвестной, вычислительные эксперименты показали, что не существует контрпримера с числом вершин менее 86. ^{[ 4 ]}

Если гипотеза Барнетта окажется ложной, то можно показать, что она NP-полна, чтобы проверить, является ли двудольный кубический многогранник гамильтоновым. ^{[ 5 ]} Если планарный граф двудольный и кубический, но имеет только связность 2, то он может быть негамильтоновым и NP-полным для проверки гамильтоновости этих графов. ^{[ 6 ]} Другой результат был получен Alt et al. (2016) : если двойственный граф может быть раскрашен вершинами в синий, красный и зеленый цвета так, что каждый красно-зеленый цикл содержит вершину степени 4, то первичный граф является гамильтоновым.

Связанные проблемы

Связанная с этим гипотеза Барнетта гласит, что каждый кубический многогранный граф, в котором все грани имеют шесть или меньше ребер, является гамильтоновым. Вычислительные эксперименты показали, что если бы контрпример существовал, то он должен был бы иметь более 177 вершин. ^{[ 7 ]} Гипотезу доказал Кардош (2020) .

Пересечение этих двух гипотез будет состоять в том, что каждый двудольный кубический многогранный граф, в котором все грани имеют четыре или шесть ребер, является гамильтоновым. Это было подтверждено Гуди (1975) .

Примечания

^ Все (1971) ; Хортон (1982) .
^ См . Alt et al. (2016) за доказательства
^ Флорек (2010) .
^ Холтон, Манвел и Маккей (1985) ; Хертель (2005) .
^ Федер и Суби (2006) .
^ Акияма, Нисидзеки и Сайто (1980) .
^ Альдред и др. (2000) .

Ссылки

Акияма, Таканори; Нисидзеки, Такао ; Сайто, Нобудзи (1980), «NP-полнота проблемы гамильтонова цикла для двудольных графов» , Journal of Information Processing , 3 (2): 73–76, MR 0596313
Альт, Хельмут ; Пейн, Майкл С.; Шмидт, Йенс М.; Вуд, Дэвид Р. (2016), «Мысли о гипотезе Барнетта» (PDF) , Австралазийский журнал комбинаторики , 64 (2): 354–365, MR 3442496
Олдред, REL; Бау, С.; Холтон, Д.А.; Маккей, Брендан Д. (2000), «Негамильтоновы 3-связные кубические плоские графы», SIAM Journal on Discrete Mathematics , 13 (1): 25–32, doi : 10.1137/S0895480198348665 , MR 1737931
Барнетт, Дэвид В. (1969), «Гипотеза 5», в Тутте, WT (ред.), Недавний прогресс в комбинаторике: материалы Третьей конференции по комбинаторике Ватерлоо, май 1968 г. , Нью-Йорк: Academic Press, MR 0250896
Федер, Томас; Суби, Карлос (2006), О гипотезе Барнетта , ECCC TR06-015
Флорек, Ян (2010), «О гипотезе Барнетта», Discrete Mathematics , 310 (10–11): 1531–1535, doi : 10.1016/j.disc.2010.01.018 , MR 2601261
Гуди, PR (1975), «Гамильтоновы схемы в многогранниках с четными гранями», Israel Journal of Mathematics , 22 (1): 52–56, doi : 10.1007/BF02757273 , MR 0410565
Гертель, Александр (2005), Обзор и усиление гипотезы Барнетта (PDF)
Холтон, Д.А.; Манвел, Б.; Маккей, Б.Д. (1985), «Гамильтоновы циклы в кубических 3-связных двудольных плоских графах», Журнал комбинаторной теории, серия B , 38 (3): 279–297, doi : 10.1016/0095-8956(85)90072-3 , МР 0796604
Хортон, JD (1982), «О двух факторах двудольных регулярных графов», Discrete Mathematics , 41 (1): 35–41, doi : 10.1016/0012-365X(82)90079-6 , MR 0676860
Кардош, Ф. (2020), «Компьютерное доказательство гипотезы Барнетта-Гуди: не только графы фуллеренов являются гамильтоновыми», SIAM Journal on Discrete Mathematics , 34 (1): 62–100, arXiv : 1409.2440 , doi : 10.1137/140984737 , S2CID 119660011
Келманс, А.К. (1994), «Конструкции кубических двудольных 3-связных графов без гамильтоновых циклов», в книге Келманс, А.К. (редактор), « Избранные темы дискретной математики: материалы Московского семинара по дискретной математике 1972–1990» , Американское математическое общество. Переводы, Серия 2, вып. 158, стр. 127–140.
Тейт, П.Г. Листинга (1884), « Топология », Философский журнал , 5-я серия, 17 : 30–46 ; Перепечатано в научных статьях , Vol. II, стр. 85–98.
Тутте, WT (1946), «О гамильтоновых схемах», Журнал Лондонского математического общества , 21 (2): 98–101, doi : 10.1112/jlms/s1-21.2.98
Тутте, WT (1971), «О 2-факторах бикубических графов», Discrete Mathematics , 1 (2): 203–208, doi : 10.1016/0012-365X(71)90027-6 , MR 0291010

Внешние ссылки

Вайсштейн, Эрик В. , «Гипотеза Барнетта» , MathWorld
Гипотеза Барнетта в саду открытых проблем, Роберт Самал, 2007.

[1] Все (1971) ; Хортон (1982) .

[2] См . Alt et al. (2016) за доказательства

[FOOTNOTEFlorek2010-3] Флорек (2010) .

[4] Холтон, Манвел и Маккей (1985) ; Хертель (2005) .

[5] Федер и Суби (2006) .

[6] Акияма, Нисидзеки и Сайто (1980) .

[7] Альдред и др. (2000) .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]