Characterizing graphs by their "walkers" Let $G$ be a (large) graph and $W$ another (smaller) graph.
$W$ is what I call a walker.
Let me use "vertices" and "edges" for $G$ and
"nodes" and "arcs" for $W$.
$W$ has a distinguished node, its center $c$.
Say that $W$ is on a vertex $v$ of $G$ if
it is placed so that node $c$ is on $v$, all
the other nodes of $W$ are on distinct vertices of $G$,
and all arcs of $W$ lie on (distinct) edges of $G$.
So $W$ is a subgraph of $G$, with $c=v$.
Now I'll describe how $W$ "walks."
If $W$ is on $v$, a step of $W$
takes $W$ to a placement on a
vertex $u$ of $G$ that is adjacent to $v$ in $G$.
So the center node $c$ of $W$ moves from $v$ to $u$,
and the remainder of $W$ is somehow laid on $G$ so that
it is again a subgraph.  Intuitively,
$W$ moves it center, and then redistributes its
"tentacles" around the new center. (One can think
of the walker as a creature that crawls around $G$.)
Finally, say that $W$ can walk $G$ if
there is a sequence of steps that moves $W$ so that
its center node $c$ is eventually on every vertex of $G$.
Thus every walkable graph is connected, because
the sequence of placements of $c$ determines a path
that covers all vertices of $G$.
Here is an example.  $G$ is an 8-vertex graph,
$W$ a 4-cycle, and the sequence below shows that $W$ can
walk $G$:

  


I am wondering to what extent the structure of $G$ (beyond its connectedness) is
determined by knowing that $W$ can walk $G$.
For example, $G$ is walkable by a $n$-star $S_n$
(with center at the star hub)
iff
$G$ has minimum degree $n$.
If $W$ is a $n$-cycle $C_n$, then certainly its 
girth
is at most $n$,
but I am not sure if walkability by $C_n$
implies any other natural structural constraint on $G$.
I also don't see what walkability by an $n$-path implies.
If anyone knows of a similar concept in the literature, I would
appreciate a reference.
Walkability is a distant abstraction of a communication network
process I was pondering.
Thanks!
 A: This could be turned into a short comment; instead I hope answer format will inspire someone to fill this out.
That every vertex is required to be in the same position of some form of subgraph makes me think that a walkable graph is to be vertex-transitive or nearly so.  Although I can probably construct rigid examples of walkable graphs, I would be more interested in knowing of connected graphs with large symmetry groups that were not walkable by any sizable graph.  Of course, any connected graph is walkable by K_2 or by S_n when n is at most the minimal degree of the graph.  Similarly, being walked by a cycle C_m means every vertex on the graph is in such a cycle; this should be a fairly limiting condition on a graph.  It might be of more interest to look at a marathon: the class of all graphs with distinguished vertices which can walk a graph.  Perhaps this could be a tool for the reconstruction conjecture or for the complexity of graph isomorphism.
Gerhard "Ask Me About System Design" Paseman, 2011.09.15 
