0

I have the below algorithm that appears to find a Hamiltonian path in undirected graphs (if one exists). I've tested with every graph I could find or come up with and it appears to work. I've included an example of it working on a decision problem graph.

I'm trying to find a counter example graph and am hoping someone here could provide one?

  1. Draw the graph, $G$, such that $\forall N \in G, N$ shares the exterior region surrounding $G$
  2. Greedy number the graph regions, $R$, formed by the regions enclosed by edges of G, R = 1,2,3....,m-1 and label the exterior region m
  3. Label each $N \in G$ as the ordered set of the joint of all number-labeled regions of G and the exterior number m that confluences at each node. Consider the number formed by the joint of the digits of each ordered set for each node, $C_{N}$. That is, $\forall N \in G,$ $C_N = (\bigcap_{i \subseteq \mathbf{I}}^{}R_{i} \oplus m ) $
  4. Begin at a random point.
  5. Connect to the nearest $C_N$ such that the nearest $C_N$ compared to the current $C_N$ is the smallest linked (shares an edge) number to the current $C_N$ yet to be connected. Move to that connected number.
  6. Repeat step 5 across $G$ until either all $C_N$ have been connected or step-5 cannot continue.
  7. Check both ends of the path made cannot continue as per steps 5-6.
  8. If the other end of the path can continue as per steps 5-6 then repeat from 5 beginning from the path's other end until all nodes are connected at least once.
  9. If all nodes can be connected in a path then there is a connected path, otherwise there is not a connected path.

Example

Ben
  • 1
  • 1
    In steps 1,2 you seem to assume that graph is planar or even stronger outerplanar. – Michal Adamaszek Feb 20 '24 at 09:07
  • I morph the graph to outerplanar. Which can be tricky at the best of times. – Ben Feb 20 '24 at 21:17
  • It can be tricky because it is not always possible. – Michal Adamaszek Feb 21 '24 at 06:20
  • You can always draw a graph such that every node is an exterior node. – Ben Feb 21 '24 at 07:33
  • If you allow the edges to intersect arbitrarily in the drawing then yes, but then it is hard to talk about the "regions" and even "exterior" in a natural way so perhaps you should define what they mean. Maybe you can explain how your algorithm works on the graph $K_{3,3}$. – Michal Adamaszek Feb 21 '24 at 07:44
  • apologies in advance for the poor diagram, but it works. https://imgur.com/a/e1ULSuR – Ben Feb 21 '24 at 08:03
  • And here is the Thomsen graph (previous comment had a central node)- working also. Each node connects to the next smallest number which shares and edge. https://imgur.com/msKgSNS – Ben Feb 26 '24 at 03:30
  • It seems if you always commence from the largest labelled node it works on bipartite graphs? Which would mean a minor adjustment to the algorithm. Im still yet to find a graph this approach doesn't work with after 18 days of searching. – Ben Mar 10 '24 at 05:34

0 Answers0