1
$\begingroup$

How would this graph be classified? And what properties does it have? What would be a natural thing to study with this graph? I know it has 40 nodes. It's undirected. It's planar if I'm not mistaken. Also this graph looks like it's 4-connected except for the 4 outer most nodes.

I read on Wikipedia that: "4-connected planar graphs are always Hamiltonian by a result due to Tutte, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time." Are 4-connected planar graphs somehow easier to compute Hamiltonian cycles for?

I'm wondering if that result is valid for this graph because 4 nodes have degree 6, while the others have degree 4. Thanks for your help.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ It is very easy to find a Hamiltonian cycle in this graph. First find a cycle in the inner 6x6 grid graph. Then replace four of the outer edges with detours to the 4 extreme nodes. $\endgroup$ – Jaap Scherphuis May 29 '18 at 8:31
  • $\begingroup$ Or add four edges to the outside connecting the extreme nodes? $\endgroup$ – Ultradark May 30 '18 at 0:27
  • $\begingroup$ I don't understand what you mean - that would be changing the graph. I'm talking about finding a Hamiltonian cycle in the exact graph you pictured. If you want to to ask about a different graph, you should ask a different question. $\endgroup$ – Jaap Scherphuis May 30 '18 at 7:03

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.