# Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of Hamiltonian Path problems is NOT known. Some of those classes are 2-connected cubic planar graphs, circle graphs and triangular grid graphs.

Also, I found in the graph classes database a weird case of solid grid graphs where Hamiltonian cycle problem is in $P$ while Hamiltonian path problem is of unknown complexity.

Is there a graph class, listed in the above database of graph classes, where Hamiltonian Cycle and Hamiltonian Path problems have different complexity? Is there an explanation for this phenomena?

I am looking for a graph class, listed in the above database of graph classes, where one of the two problems is known to be polynomial-time solvable while the other is known to be $NP$-complete when inputs are restricted to this class of graphs.

I posted essentially a similar question on CS theory Stackexchange with no satisfactory answer.

• Take the class of graphs that have at least one vertex of degree 1. The complexity of HC is constant on this class, whereas HP is NPC. – Michal R. Przybylek Dec 18 '13 at 21:09

There are silly examples. Consider the class "graphs that have a degree $1$ vertex". These can never have a Hamiltonian cycle, so the cycle problem is in $P$. If $G$ is $H$ with one extra vertex $u$ neighboring the vertex $v$ of $H$, then $G$ has a Hamiltonian path if and only if $H$ has a Hamiltonian path starting in $v$, and that's NP-complete. (If we had a polynomial time algorithm for testing whether a graph with $n$ vertices had a Hamiltonian path starting at a particular vertex, then running this algorithm $n$ times would be a polynomial time algorithm for whether the graph had a Hamiltonian path.)