Подсчет количества гамильтоновых циклов в кубических гамильтоновых графах?

Это -трудного найти постоянный коэффициент приближение длинного цикла в кубических гамильтоновых графах. Кубические гамильтоновы графы имеют как минимум два гамильтоновых цикла.$NP$

Каковы наиболее известные верхняя и нижняя границы числа гамильтоновых циклов в кубических гамильтоновых графах? Учитывая кубический гамильтонов граф, какова сложность нахождения числа гамильтоновых циклов? Это # -hard?$P$

Подсчет гамильтоновых цепей в 3-правильном гамильтоновом графе является # P-полным, как показано ниже.

Эскиз доказательства . Членство в #P тривиально, поэтому мы покажем только # P-hardness.

Раздел 3 Liśkiewicz, Ogihara и Toda [LOT03] показывает, что подсчет гамильтоновых цепей в 3-регулярном (и фактически плоском в то же время) графе является # P-полным. Кроме того, их редукция из # 3SAT отображает выполнимую формулу 3CNF в гамильтоновы графы. Следовательно, вы можете уменьшить # 3SAT до подсчета гамильтоновых цепей в 3-регулярном гамильтоновом графе, сначала добавив одно тривиальное решение к заданной формуле 3CNF, а затем сократив его до подсчета гамильтоновых цепей, используя сокращение в [LOT03]. КЕД .

[LOT03] Мацей Лицкевич, Мицунори Огихара и Сейносукэ Тода. Сложность подсчета самоходных прогулок в подграфах двумерных сеток и гиперкубов. Теоретическая информатика , 304 (1–3): 129–156, июль 2003 г. http://dx.doi.org/10.1016/S0304-3975(03)00080-X

$2^{3n/8}$$2^{n/3}$$2^{n/3}$$1.276^n$

$2^{n/2}$

Некоторые графики имеют ровно три гамильтоновы схемы:

http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract

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

Дополнительный комментарий:

Также была проведена некоторая работа по вопросу о том, какие графы, кроме циклов, имеют ровно одну гамильтоновую цепь:

http://www3.interscience.wiley.com/journal/113386600/abstract

Очень хорошая обзорная статья о контурах hamltionian в специальных видах графиков, в которой есть раздел, посвященный количеству гамильтоновых схем, и исправляет некоторые проблемы, приведенные в статье выше:

http://ajc.maths.uq.edu.au/pdf/20/ajc-v20-p111.pdf