<p>In my paper "The traveling salesman problem for cubic graphs" (<a href="http://arxiv.org/abs/cs.DS/0302030">J. Graph Algorithms and Applications 11(1):61-81, 2007</a>) 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", <a href="http://siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf">ANALCO 2008</a>) improved the upper bound to $1.276^n$.</p>

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

CC BY-SA 2.5
2010-11-22T18:00:02.117Z
Thanks David for the nice answer, I wish I could accept more than one answer.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-23T16:15:46.600Z
2010-10-23T20:14:07.200Z
2010-10-23T20:14:07.200Z
David Eppstein
<p>Some graphs have exactly three hamiltonian circuits:</p>

<p><a href="http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract">http://onlinelibrary.wiley.com/doi/10.1002/jgt.3190060218/abstract</a></p>

<p>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.</p>

<p>Additional comment:</p>

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

<p><a href="http://www3.interscience.wiley.com/journal/113386600/abstract">http://www3.interscience.wiley.com/journal/113386600/abstract</a></p>

<p>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:</p>

<p><a href="http://ajc.maths.uq.edu.au/pdf/20/ajc-v20-p111.pdf">http://ajc.maths.uq.edu.au/pdf/20/ajc-v20-p111.pdf</a></p>

CC BY-SA 2.5
2010-10-24T12:38:38.890Z
2010-10-24T17:42:03.560Z
2010-10-24T17:42:03.560Z
Joseph Malkevitch
<p>Counting Hamiltonian circuits in a 3-regular Hamiltonian graph is #P-complete, as follows.</p>

<p><strong>Proof sketch</strong>.  The membership in #P is trivial, so we will only show the #P-hardness.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat">adding one trivial solution</a> to a given 3CNF formula and then reducing it to counting Hamiltonian circuits by using the reduction in [LOT03].  <strong>QED</strong>.</p>

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

CC BY-SA 2.5
2010-10-23T13:33:01.130Z
Nice answer. Are you aware of any upper bound or lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-23T13:47:48.153Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-23T12:46:34.710Z
2010-10-23T12:46:34.710Z
2017-04-13T12:32:28.117Z
Tsuyoshi Ito
<p>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.</p>

<blockquote>
  <p>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? </p>
</blockquote>

<cc.complexity-theory><counting-complexity>
Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?
Mohammad Al-Turkistany
# Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

(Asked by: username_0 on 2010-10-22)

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?

**Tags:** cc.complexity-theory, counting-complexity

---

## 3 answers

### Answer by username_3 on 2010-10-23. Score: 20 | Accepted answer

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](https://cstheory.stackexchange.com/questions/1639/verifying-unique-solutions-of-sat) 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>

> **Comments:**
> **username_0**: Nice answer. Are you aware of any upper bound or lower bound on the number of Hamiltonian cycles in cubic Hamiltonian graphs?  
> **username_3**: @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.  

---

### Answer by username_1 on 2010-10-23. Score: 24

In my paper "The traveling salesman problem for cubic graphs" ([J. Graph Algorithms and Applications 11(1):61-81, 2007](http://arxiv.org/abs/cs.DS/0302030)) 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](http://siam.org/proceedings/analco/2008/anl08_023gebauerh.pdf)) 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.

> **Comments:**
> **username_0**: Thanks David for the nice answer, I wish I could accept more than one answer.  

---

### Answer by username_2 on 2010-10-24. Score: 8

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>


---

