0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I meant, could there be some possible Hamiltonian circuits I'm not thinking of, that could be followed (with some memory), even if the car have no initial knowledge? $\endgroup$ – dEmigOd Jun 17 at 19:13
  • $\begingroup$ No. If the car starts at (1,1) and moves North to (1,0), it doesn't know that it needs to next go West to (0,0). It's possible to get lucky, but impossible to guarantee that it makes the right turn. $\endgroup$ – Spitemaster Jun 17 at 19:17
  • $\begingroup$ Now, I'm not sure. What if in your axes, I always go counter-clockwise on the edge (until some counter expires)? $\endgroup$ – dEmigOd Jun 17 at 19:46
  • $\begingroup$ Then you'll end up at (0,0) and have nowhere to go. For any Hamiltonian circuit on a rectangular graph like that, the path must go through both adjacent vertices. It's impossible to guarantee that it will. $\endgroup$ – Spitemaster Jun 17 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.