On 4-Regular Planar Hamiltonian Graphs

In order to research knots with large crossing numbers, one would like to be able to select a random knot from the set of all knots with n crossings with as close to uniform probability as possible. The underlying graph of a knot diagram can be viewed as a 4-regular planar graph. The existence of a Hamiltonian cycle in such a graph is necessary in order to use the graph to compute an upper bound on rope length for a given knot. The algorithm to generate such graphs is discussed and an exact count of the number of graphs is obtained. In order to allow for the existence of such a count, a somewhat technical definition of graph equivalence is used. The main result of the thesis is the asymptotic results of how fast the number of graphs with n vertices (crossings) grows with n.

Name thesis:degree_name

Master of Science

Discipline thesis:degree_discipline

Department of Mathematics and Computer Science

Year

2006

Author dc:creator

• High, David

• Applied Mathematics

Repository record dc:identifier

https://digitalcommons.wku.edu/theses/277

OAI identifier oai:identifier

oai:digitalcommons.wku.edu:theses-1280