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.

  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.