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$:
   Graph Walking
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!

  • $\begingroup$ 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 $\endgroup$ – Gerhard Paseman Sep 15 '11 at 23:54
  • $\begingroup$ @Gerhard: Coincidence. I did consider making that a requirement, but it felt too constraining. One can imagine many rules... $\endgroup$ – Joseph O'Rourke Sep 16 '11 at 0:10
  • $\begingroup$ 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$.) $\endgroup$ – Autumn Kent Sep 16 '11 at 13:34
  • $\begingroup$ @Richard: I like this "walking complex" viewpoint! Thanks for the suggestion. $\endgroup$ – Joseph O'Rourke Sep 16 '11 at 15:41
  • $\begingroup$ @Joseph: Sure thing! $\endgroup$ – Autumn Kent Sep 16 '11 at 16:21

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

  • $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Sep 16 '11 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.