Which Grids are Hamiltonian
Sandra Hedetniemi, Stephen Hedetniemi, Peter Slater
Committee:
Technical Report(May 1980)
Keywords:

A complete grid Gm,n is a graph having m x n vertices which are connected to form a rectangular lattice in the plane, i.e. all edges of Gm,n connect vertices along horizontal or vertical lines. A grid is a subgraph of a complete grid. We study the existence of Hamiltonian cycles in complete grids and complete grids with one or two vertices removed.