# 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!

• In your example, the center travels on a Hamiltonian path. Coincidence, or is this a desirable property to call out? ("Power walking" perhaps?) Gerhard "Ask Me About Power Sitting" Paseman, 2011.09.15 – Gerhard Paseman Sep 15 '11 at 23:54
• @Gerhard: Coincidence. I did consider making that a requirement, but it felt too constraining. One can imagine many rules... – Joseph O'Rourke Sep 16 '11 at 0:10
• Idle thought: would it be of any help to study the "walking complex" $C(G,W)$ for $G$ and $W$, namely, the graph whose vertices are the pointed subgraphs of $G$ isomorphic to $W$, and whose edges are single steps? So, if $W$ is a vertex, this graph is just $G$, but at the other end the components seem to tell tell you something about the pointed automorphisms of $G$. (Also, you could add higher dimensional cells to $C(G,W)$ by declaring that it be a flag complex, and it would be cool to see what it's homology says about $G$.) – Autumn Kent Sep 16 '11 at 13:34
• @Richard: I like this "walking complex" viewpoint! Thanks for the suggestion. – Joseph O'Rourke Sep 16 '11 at 15:41
• @Joseph: Sure thing! – Autumn Kent Sep 16 '11 at 16:21

• Thanks for your stimulating thoughts, Gerhard! Re your reconstruction point: I wonder to what extent $G$ is determined from knowing the complete set of all $W$ that walk $G$? Definitely underdetermined, but it provides some constraints. – Joseph O'Rourke Sep 16 '11 at 11:37