Question

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!

Answer 1

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