Hamiltonian circuits on rectangular graphs

171 Views Asked by At

Let $G=(V,E)$ be a rectangular graph on $n \times m$ vertices.

It is easy to show that no Hamiltonian circuit exists for $n,m$ odd, and pretty easy to build a circuit for graph with at least one even side.

(Below are my hits on $6 \times 7$ rectangular graph)

Circuit in thick

Circuit in thick

Another circuit in thick

... and I suppose there are quite a few circuits. (Is it hard to enumerate them, also?)

My main interest, is as follows. Suppose I have a car riding in this "Manhattan"-like city. The car is unaware of true sizes, except, maybe, to which one is even, so it could imagine to itself appropriate circuit on the streets.

Is it true, that being unaware of actual sizes, and equipped with enough memory, there exists a Hamiltonian circuit, which the car with visibility $= 1$ is able to follow?

The above circuits seem to be appropriate for cars with visibility $= 2$ (except the last one, which I think, requires $3$).

Where visibility $= 1$ is just seeing $4$ immediate neighbors, so not riding in the first column - it has (maybe) no awareness of column index (except it can track for some time, due to memory).

If it helps, I want to move the car in discrete steps, from vertex to vertex.

1

There are 1 best solutions below

4
On BEST ANSWER

Either the car is aware of its initial position (in which case, the problem is easy) or else upon reaching an edge a car with visibility 1 is unable to correctly determine which way to turn. Thus I believe the answer to your question is no.