Cycle Spectrums in Honeycomb Toroidal Graphs
By Joshua Connor, University of Newcastle
Graph theory is a relatively new area of mathematics. Euler’s paper published in 1736 on the “Seven Bridges of Königsberg” is regarded as the first ever in the field of graph theory. One of the pleasing benefits of graph theory is that it is easily visualised and does not require much maths to be able to understand the basics.
To introduce my project, let us travel back to 1736 and try to understand why it arose. Imagine you live in a city that is made up of many islands each connected to the other islands by a number of bridges. You plan on going for a walk with your new love interest, who happens to be a budding young civil engineer, and you wish to impress them by showing them all the bridges of the city. But you have one problem; if you show them a bridge twice they will not be as excited as showing them a new bridge each time. Can you walk from your house, cross every bridge exactly once and return home again?
In order to solve this problem, Euler imagined each island as a dot (or vertex), and if there was a bridge connecting two islands then he drew a line (or edge) between then. This gives you a simple idea of what is known as a graph: a number of vertices, arranged in some fashion, joined together by edges.
The problem you face is that you wish to return home AND only visit the bridges once each. This is equivalent to a postman who wishes to visit a number of houses and return home. In graph theory, this is called a cycle. A cycle exists in a graph when you can start at one vertex, visit at least two others and return home. The length of a cycle is determined by the number of vertices in it. For example, a cycle of length 7 would contain exactly 7 vertices.
My project looked at the length of cycles present in one very particular class of graphs, honeycomb toroidal graphs. Honeycomb because each “face” in the graph is a hexagon, toroidal because it can be drawn on a torus (picture a donut) without having its edges cross.
In short we were able to prove that all honeycomb toroidal graphs have no odd length cycles, they have every even length cycle that is NOT a multiple of four, and they only have cycles of length that are multiples of four if they meet some very specific criteria. We know from a computer search that there are some graphs that miss cycles whose length is a multiple of four, such as 8, 12, etc., but we are yet to prove exactly when this occurs.
This project was a wonderful experience in mathematical research and has convinced me that it is a career path I wish to pursue. I would like to thank my supervisors Brian Alspach and Thomas Kalinowski for guiding me along, and the Australian Mathematical Sciences Institute for supporting me financially and inviting me to present at AMSIConnect. I highly recommend it to any undergraduate interested in research.
Joshua Connor was one of the recipients of a 2016/17 AMSI Vacation Research Scholarship.