Definition: Define the $k$-HamiltonianCycles problem as the decision problem that asks if a given graph has at least $k$ distinct Hamiltonian cycles.

Question: Is there some constant $k$ so that the $k$-HamiltonianCycles problem is $NP$-complete on the class of planar $4$ connected graphs? In particular, what about $k = 3$? If not, what about $k = 4$?

Motivation: It is well known that $1$-HamiltonianCycles is $NP$-complete on the class of planar $3$-connected graphs. On the other hand, all planar $4$-connected graphs have a Hamiltonian cycle, by Tutte.

Additionally, it is known that a $4$-connected planar graph $G$ is "Hamiltonian Connected." That is, given any two vertices, $x$ and $y$, there is a Hamiltonian $xy$-path in $G$. This implies that a $4$-connected planar graph always has at least $2$ Hamiltonian cycles. Given one cycle, say $C$, let $e$ be an edge not in $C$. If $\gamma$ is the Hamiltonian path between the endpoints of $e$, we can extend it to a Hamiltonian cycle containing $e$.

If the $4$ connected planar graph $G = (V,E)$ has at least one vertex of degree $\geq 5$, then by $4 |V| > \sum_{v \in V} deg(v) = 2|E|$, $|E| > 2|V|$. This implies that there is an edge not in the union of any two Hamiltonian cycles of $G$, so that one is guaranteed a third Hamiltonian cycle by the same argument as in the previous paragraph. Since a planar graph has at most $3n - 6$ edges, one cannot repeat this to guarantee the existence of a fourth Hamiltonian cycle.

I don't know if there is an argument guaranteeing that all $4$-connected planar graphs have at least $3$ Hamiltonian cycles, or if there is a different kind of argument guaranteeing that all $4$-connected planar graphs have at least $4$ Hamiltonian cycles. I am wondering if these problems, or similar ones, are $NP$-complete.

This question is similar, but not the same: https://mathoverflow.net/questions/233476/what-is-the-complexity-of-finding-a-third-hamilton-cycle-in-cubic-graph


Your Answer

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

Browse other questions tagged or ask your own question.