# Hamiltonian cycle on graphs without small cycles

While answering this question on cstheory, I (informally) proved on the fly the following theorem:

Theorem: For any fixed $l \geq 3$ the Hamiltonian cycle probem remains NP-complete even if restricted to planar bipartite undirected graphs of maximum degree 3 that don't contain cycles of length $\leq l$.

It seems very unlikely that it has not already appeared somewhere.
But it allows to settle many Hamiltonian cycle/path problems on graphclasses.org that are marked as "Unknown to ISGCI" (see for example this one); indeed a direct corollary is that Hamiltonian cycle and path problems are still NP-complete if restricted to $(H_1,...,H_k)\text{-free}$ graphs, where each of the $H_i$ contains at least one cycle.

Can you give me a reference of the paper/book where it appeared?

(then I'll contact people at graphclasses.org)

-
At least these discussions helped for new results in graphclasses.org so please inform graphclasses about unknown to them result - The Contact link gives a form, email address is optional. – joro Jun 18 '14 at 8:02
@joro: I already contacted them, yesterday (I also gave them my email). I'll wait a few days and see if they update the status of those problems. – Marzio De Biasi Jun 18 '14 at 8:42
I heard they don't update the database very often and reply with "thanks" after updating the DB and they are quite responsive. – joro Jun 18 '14 at 9:04
@joro: I think they updated the database (they are very collaborative and polite) – Marzio De Biasi Jun 23 '14 at 7:27

The result is stated in the paper Two New Classes of Hamiltonian Graphs by Arkin, Mitchell and Polinshchuk.

-

This unpublished manuscript by Hougardy, Emden-Weinert and Kreuter in 1997 provided a simple proof for the following result which is much stronger than the result pointed out in Kristoffer Arnsfelt Hansen's answer:

For any given rational number $0\le r <1/2$, the Hamiltonian cycle probem remains NP-complete even if restricted to bipartite planar $n$-vertex graphs of maximum degree 3 and girth $\ge n^r$.

The manuscript contains also similar results for other problems such as Dominating set, Max cut, VFS, etc.

-
Ok, thanks! I forgot to mention that my proof works for planar undirected bipartite graphs of max-degree 3 ... so the Hourgardy et al. paper is stronger ... but not much stronger :-) :-). I'll probably accept Kristoffer's answer because he posted it first. – Marzio De Biasi Jun 17 '14 at 17:00
No problem :-)) – vb le Jun 17 '14 at 17:13
@MarzioDeBiasi, I think the strongness is about the size of a girth. your proof is about fixed number, accepted answer is for some f(n) which is less than sqrt and this answer is more general than all of them. (IMHO restriction to the graph is not very important here) – Saeed Jun 17 '14 at 21:26
The paper contains other NP-hard problems, it will be an answer to the linked question about cyclic graphs. – joro Jun 18 '14 at 9:08