Generalization of walks into graphs

45 Views Asked by At

When we have a graph with cycles, a walk is like a kind of path possibly unfolding some cycles. A special case in programming would be something like an execution going through some loops a certain number of times.

I would like to know if a kind of generalization of walks into graphs as described below exists in the litterature and if it has a name. It would be something like a kind of "unfolding/expansion" of a given graph. If we have a graph $G$, we are looking for a graph $\mathtt{unfold}(G)$ such that each path in $\mathtt{unfold}(G)$ corresponds to a walk in $G$. For instance:

enter image description here

Left : $G$ Right : $\mathtt{unfold}(G)$

We can make a chain of any size with the node $2$ and with the cycle $(1, 3, 4)$. We can connect two such chains with an edge between a node $1$ and a node $2$.