0
$\begingroup$

enter image description here

In the above graph, the blue line shows a cycle of length $84$, the remaining edges are higlihtged in red. In total, the graph has $100$ vertices and $143$ edges.

  • Is this the longest cycle in this graph ?

The graph has no hamilton cycle because deleting the vertices $8$ and $20$ splits the graph into $3$ components. Deleting the vertices $1,5,8,13,20,22,25,37$ splits the graph into $10$ components, so it contains not even a hamiltonian path.

  • How can I get the length of the longest cycle ?
$\endgroup$
  • $\begingroup$ The easiest way would be to enter the graph into Sage math and call longest_cycle() $\endgroup$ – Jernej Sep 27 '14 at 16:28
  • $\begingroup$ Sagemath is freely available to download or use through Sage cloud - cloud.sagemath.com In case you still do not wish to use it I can do it for you if you provide the edges of your graph in a .txr file $\endgroup$ – Jernej Sep 27 '14 at 18:06
  • $\begingroup$ You can use it through you web browser by registering on the link, otherwise it is relatively messed up for windows users. $\endgroup$ – Jernej Sep 27 '14 at 18:46
  • $\begingroup$ I am sorry, I meant a .txt file. A simple file that contains the edges in a format that is easy to parse - say dimacs format. $\endgroup$ – Jernej Sep 27 '14 at 19:05
  • $\begingroup$ btw, are you trying to find small planar hypohamiltonian graphs? :) $\endgroup$ – Jernej Sep 27 '14 at 19:08

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.