  We give lower bounds for various natural node- and edge-based local
strategies for exploring a graph. We consider this problem both in the setting
of an arbitrary graph as well as the abstraction of a geometric exploration of
a space by a robot, both of which have been extensively studied. We consider
local exploration policies that use time-of-last- visit or alternatively
least-frequently-visited local greedy strategies to select the next step in the
exploration path. Both of these strategies were previously considered by Cooper
et al. (2011) for a scenario in which counters for the last visit or visit
frequency are attached to the edges. In this work we consider the case in which
the counters are associated with the nodes, which for the case of dual graphs
of geometric spaces could be argued to be intuitively more natural and likely
more efficient. Surprisingly, these alternate strategies give worst-case
superpolynomial/ exponential time for exploration, whereas the least-frequently
visited strategy for edges has a polynomially bounded exploration time, as
shown by Cooper et al. (2011).
