Cycles in Grid Graphs and Toroidal Variants*
Presentation Type
Poster Presentation
Mentor/Supervising Professor Name
Bosman, Anthony
Abstract (Description of Research)
A grid graph is an integer lattice with edges between adjacent vertices. We show that there exists a Hamiltonian path on a 3-dimensional grid graph exactly when all the dimensions are even. Then we take up three topological variants, forming toroidal grid graphs by identifying opposite faces of the grid graph, either identifying one, two, or all three pairs of opposite faces. In these settings, we determine the parity of a cycle’s length that exists on the toroidal grid graph in terms of the dimensions of the graph and the number of times the cycle passes through each pair of identified faces. This allows us to exhibit examples of Hamiltonian cycles in toroidal grid graphs.
Cycles in Grid Graphs and Toroidal Variants*
A grid graph is an integer lattice with edges between adjacent vertices. We show that there exists a Hamiltonian path on a 3-dimensional grid graph exactly when all the dimensions are even. Then we take up three topological variants, forming toroidal grid graphs by identifying opposite faces of the grid graph, either identifying one, two, or all three pairs of opposite faces. In these settings, we determine the parity of a cycle’s length that exists on the toroidal grid graph in terms of the dimensions of the graph and the number of times the cycle passes through each pair of identified faces. This allows us to exhibit examples of Hamiltonian cycles in toroidal grid graphs.