Tracing a Hamiltonian Cycle on the 3-6 Graph on 18 Vertices

A few weeks ago I constructed a 3-6 graph on 18 vertices. My strategy then was to start with 3 sets of 6 vertices, two of which were already connected to form a Hamilton cycle of length 6. My object then was to interconnect the vertices to create a 3-6 graph, and I was able to do this successfully.

 Graph A

My adviser then wanted me to rearrange the vertices to see if there existed a Hamiltonian graph of length 18 in the above 3-6 graph I had drawn. I was able to successfully rearrange the vertices to clearly illustrate that there was one (image below).

Graph B

He also asked me to write an algorithm so that starting at any vertex, I could trace the Hamilton cycle of length 18. The algorithm is included below.

Algorithm:

Name the following three groups of vertices in Graph A.
Outer Vertices {C, I, L, D, R, O}
Middle Vertices {F, H, K, N, Q, A}
Inner Vertices {B, G, J, E, P, M}

Choose any vertex in Graph A

You can start anywhere in the pattern and it loops until you have returned to your starting vertex. The following two rules must also be kept:

1) Visit each vertex once and only once

2) The first time you travel Middle-Middle or Outer-Outer sets the direction you will travel throughout the cycle (clockwise or counterclockwise). Once set, this direction must always be followed.

Pattern:
Outer
Inner
Middle
Middle
Inner
Outer

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: