  We consider the problem of exploration of an anonymous, port-labeled,
undirected graph with $n$ nodes and $m$ edges and diameter $D$, by a single
mobile agent. Initially the agent does not know the graph topology nor any of
the global parameters. Moreover, the agent does not know the incoming port when
entering to a vertex. Each vertex is endowed with memory that can be read and
modified by the agent upon its visit to that node. However the agent has no
operational memory i.e., it cannot carry any state while traversing an edge. In
such a model at least $\log_2 d$ bits are needed at each vertex of degree $d$
for the agent to be able to traverse each graph edge. This number of bits is
always sufficient to explore any graph in time $O(mD)$ using algorithm
Rotor-Router. We show that even if the available node memory is unlimited then
time $\Omega(n^3)$ is sometimes required for any algorithm. This shows that
Rotor-Router is asymptotically optimal in the worst-case graphs. Secondly we
show that for the case of the path the Rotor-Router attains exactly optimal
time.
