Posts Tagged ‘ Hamiltonian cycle ’

Thesis Draft 5

From here on, each draft of my thesis will be constructed using PCTeX.

Thesis Draft 5

Thesis Draft 4 (PCTeX)

Dr. Sharma asked me to rewrite what I had so far for my thesis using PCTeX. PCTeX is a software that uses TeX, a mathematical language, to produce documents. I have been learning the software and language as I go, so these drafts are truly works in progress.

Thesis Draft 4 (PCTeX)

Thesis Draft 3

This draft reflects the new organization of my thesis and main topics we aim to cover. Some of the topics have already been discussed, but I did not have time to add them to this draft of the paper. See blog posts for up-to-date information on what topics I have already researched.

Thesis Draft 3

LCF Notation

I’m doing some research on LCF notation to see how it relates mathematics to chemistry. LCF notation was originally developed by Joshua Lederberg as a way to represent cyclic graphs in chemistry. It was further developed by Coxeter and Frucht, who dubbed the notation LCF. Here is the original paper written by Lederberg that first uses the notation.

Lederberg Paper

Thesis Draft 2: Examples and LCF Notation

After meeting with my adviser, he suggested some changes for my terminology section and added some new sections. I have now also included personal examples of cubic graphs that I have drawn and LCF notation.

Thesis Draft 2: Examples and LCF Notation

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

3-6 Graph on 16 Vertices

Last week I was challenged to draw a 3-g Graph on 16 vertices. I managed to draw a 3-5 graph, but after talking with my advisor, realized that because 3-6 cage is on 14 vertices, there existed a 3-6 graph on 16 vertices. So below is my construction of a cubic graph on 16 vertices with the maximum girth (6).

%d bloggers like this: