Гамильтоновость кубического графа

[Alexander Evnin]

Известны ли какие-либо критерии гамильтоновости для кубического графа?

В частности, является ли следующий граф на 46 вершинах гамильтоновым?

[matemat]

Что Вам мешает взять условие существования гамильтонова цикла и проверить?

[whitefox]

Alexander Evnin в сообщении #1178096 писал(а):

Известны ли какие-либо критерии гамильтоновости для кубического графа?

В WikipediA не смотрели?

[grizzly]

whitefox в сообщении #1178134 писал(а):

В WikipediA не смотрели?

А там как-то на удивление скромно с информацией. Нужно гуглить статьи, работ в этом направлении море (хотя результатов меньше). Из того, что мне недавно попадалось на глаза, известно:

Если 3-связный плоский кубический граф не имеет более чем 6-сторонних граней, то он гамильтонов.

Это в какой-то статье про фуллерены было. К представленному графу критерий, понятно, не подходит.

-- 18.12.2016, 20:19 --

Вот здесь.

[matemat]

grizzly в сообщении #1178147 писал(а):

whitefox в сообщении #1178134 писал(а):

В WikipediA не смотрели?

А там как-то на удивление скромно с информацией.

Но там есть подсказка:

Цитата:

There has been much research on Hamiltonicity of cubic graphs. In 1880, P.G. Tait conjectured that every cubic polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Tait's conjecture, the 46-vertex Tutte graph, in 1946. In 1971, Tutte conjectured that all bicubic graphs are Hamiltonian.

которая приводит к Grinberg's theorem.

[Alexander Evnin]

Да, оказалось, что всё дело в этой теореме. https://en.wikipedia.org/wiki/Grinberg%27s_theorem