1
$\begingroup$

I am wondering if this is a topic that has had research done...

If I could reduce irregular graphs to regular graphs (including replacing redundant node clusters with dummy nodes), while ensuring that hamiltonicity wouldn't be lost - that would be very useful for me.

Anyone know anything about this? Thank you.

$\endgroup$
  • $\begingroup$ Yes, there is a reduction to 3-regular graphs. See this paper [delivery.acm.org/10.1145/810000/803884/p47-garey.pdf] on the page numbered 54. $\endgroup$ – GMB Sep 26 '18 at 23:07
  • 1
    $\begingroup$ link isn't working for me. what is the name of the paper? $\endgroup$ – Travis Black Sep 27 '18 at 3:52
  • 2
    $\begingroup$ Oops -- it's "The Planar Hamiltonian Circuit Problem is NP-Complete" by Garey, Johnson, Tarjan (see also references within which might have more direct/alternate proofs). $\endgroup$ – GMB Sep 27 '18 at 14:40

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.