<p>I am wondering if this is a topic that has had research done...</p>

<p>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.</p>

<p>Anyone know anything about this?  Thank you.</p>

CC BY-SA 4.0
2018-09-26T23:07:48.437Z
Yes, there is a reduction to 3-regular graphs.  See this paper [http://delivery.acm.org/10.1145/810000/803884/p47-garey.pdf] on the page numbered 54.
GMB
CC BY-SA 4.0
2018-09-27T03:52:51.543Z
link isn't working for me.  what is the name of the paper?
Travis Black
CC BY-SA 4.0
2018-09-27T14:40:54.927Z
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).
GMB
<graph-theory><graph-algorithms><reductions><open-problem><hamiltonian-paths>
Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity
Travis Black
# Reduction of irregular graphs, to regular graphs, while preserving hamiltonicity

(Asked by: username_0 on 2018-09-26)

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.

**Tags:** graph-theory, graph-algorithms, reductions, open-problem, hamiltonian-paths
> **Comments:**
> **username_1**: Yes, there is a reduction to 3-regular graphs.  See this paper [http://delivery.acm.org/10.1145/810000/803884/p47-garey.pdf] on the page numbered 54.  
> **username_0**: link isn't working for me.  what is the name of the paper?  
> **username_1**: 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).  

---

## 0 answers

