5
$\begingroup$

I know that Hamiltonian cycle problem in $3$-regular triangle-free graphs is $NP$-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C_3$ cycle, what is the longest fixed-length cycle $C_g$ such that deciding the existence of Hamiltonian cycle in $3$-regular $C_g$-free graphs is still $NP$-complete?

$\endgroup$
1
$\begingroup$

Have a look at this paper "Not Being (Super)Thin or Solid is Hard: A Study of Grid Hamiltonicity" Theorem 6.1 states that HCP (Hamiltonian Cycle Problem) for planar graph of maximum degree $3$ and girth $g$ (i.e. $C_{g-1}$-free) is $NP$-complete, for arbitrary $g>6$ (i.e. $g\geq 6$ in your notation).

So, in your notation, we are left with the undetermined cases of $g=4,5$.

So if you are willing to relax $3$-regular to $\Delta(G)=3$, then $g$ (actually $g+1$ for the girth value) can be arbitrarily large.

$\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.