15
$\begingroup$

It is $NP$-hard to find a constant factor approximation of longest cycle in cubic Hamiltonian graphs. Cubic Hamiltonian graphs have at least two Hamiltonian cycles.

What are the best known upper bound and lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs? Given a cubic Hamiltonian graph, What is the complexity of finding the number of Hamiltonian cycles? Is it #$P$-hard?

$\endgroup$
20
$\begingroup$

Counting Hamiltonian circuits in a 3-regular Hamiltonian graph is #P-complete, as follows.

Proof sketch. The membership in #P is trivial, so we will only show the #P-hardness.

Section 3 of Liśkiewicz, Ogihara and Toda [LOT03] shows that counting Hamiltonian circuits in a 3-regular (and in fact planar at the same time) graph is #P-complete. Moreover, their reduction from #3SAT maps satisfiable 3CNF formula to Hamiltonian graphs. Therefore, you can reduce #3SAT to counting Hamiltonian circuits in a 3-regular Hamiltonian graph by first adding one trivial solution to a given 3CNF formula and then reducing it to counting Hamiltonian circuits by using the reduction in [LOT03]. QED.

[LOT03] Maciej Liśkiewicz, Mitsunori Ogihara and Seinosuke Toda. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science, 304(1–3):129–156, July 2003. http://dx.doi.org/10.1016/S0304-3975(03)00080-X

$\endgroup$
  • $\begingroup$ Nice answer. Are you aware of any upper bound or lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs? $\endgroup$ – Mohammad Al-Turkistany Oct 23 '10 at 13:33
  • 1
    $\begingroup$ @turkistany: You can generate a 3-regular graph with exponentially many Hamiltonian circuits by applying the above reduction to a 3CNF formula with exponentially many satisfying assignments (see Corollary 6 of [LOT03] and the definition of “$\le^p_{\text{r-shift}}$-reductions” in Section 2.2), although I suspect that there is a simpler direct proof. I do not know any lower bound except for 2 (which you already mentioned in the question) or any proof that 2 is optimal. $\endgroup$ – Tsuyoshi Ito Oct 23 '10 at 13:47
23
$\begingroup$

In my paper "The traveling salesman problem for cubic graphs" (J. Graph Algorithms and Applications 11(1):61-81, 2007) I proved an upper bound of $2^{3n/8}$ on the number of Hamiltonian cycles, conjectured that the bound could be improved to $2^{n/3}$, and found a family of graphs that have exactly $2^{n/3}$ showing that, if true, the conjectured bound would be tight. Heidi Gebauer ("On the Number of Hamilton Cycles in Bounded Degree Graphs", ANALCO 2008) improved the upper bound to $1.276^n$.

If one allows multigraphs then a cycle that alternates between single and double bonds has $2^{n/2}$ Hamiltonian cycles, and this is tight.

$\endgroup$
  • $\begingroup$ Thanks David for the nice answer, I wish I could accept more than one answer. $\endgroup$ – Mohammad Al-Turkistany Nov 22 '10 at 18:00
8
$\begingroup$

Some graphs have exactly three hamiltonian circuits:

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

If one starts with the plane graph of the tetrahedron, which contains exactly three hamiltonian circuits, and creates a new planar 3-connected graph by truncating a single vertex one gets a new graph which has exactly three hamiltonian circuits. If one continues to truncate one vertex at a time one gets a family of graphs with exactly three hamiltonian circuits.

Additional comment:

There also has been some work on the question of which graphs other than cycles have exactly one hamiltonion circuit:

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

A very nice survey paper about hamltionian circuits in special kinds of graphs which has a section dealing with numbers of hamiltonian circuits, and corrects some problems with the paper above is:

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.