Posts Tagged ‘ Norman Biggs ’

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

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

Thesis Draft 1: Terminology and Known Cubic Cages

I have begun to type up the beginning stages of my thesis, even though we have not completely defined it’s format. I know it will be focussed on the study of cubic graphs and their applications, so my adviser asked me to type up the terminology and known cubic cages sections to start with. I will be including drafts frequently as we add and change material.

Thesis Draft 1: Terminology and Known Cages

LCF Notation for 3-6 Graphs on 14, 16, and 18 Vertices

Tuesday I learned how to express Hamiltonian graphs in LCF notation. LCF notation begins with a Hamiltonian graph. From there, it shows you how to draw a cubic graph by starting at any vertex. Below is the LCF notation for the 3-6 graphs I have drawn on 14, 16, and 18 vertices.

3-6 Cage
LCF Notation [ 5, -5]^7

3-6 Cage

 3-6 Graph on 16 Vertices
LCF Notation [5, -5, 6, -5, 6, -5, 5, 6, -6, 6, -6, -5, 5, -6, 5, -6]

 3-6 Graph on 18 Vertices
LCF Notation [5, 9, -5]^6

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

%d bloggers like this: