1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ @hardmath Sorry, it wasn't very clear but during my researches I needed something similar to that and I wondered if it was actually something studied (or just appearing) in the litterature of graph theory. $\endgroup$ – Boris Jun 25 at 19:23
  • $\begingroup$ Well, "walks" on graphs can appear in a few contexts, such as the famous "shortest path" problem where edge lengths are assigned, or in network flow problems where edges are directed and capacities are assigned to edges. There are too many variants to give an exhaustive or even representative survey, so indicating a narrower scope (such as applications to program paths) would be helpful. $\endgroup$ – hardmath Jun 25 at 19:48
  • $\begingroup$ @hardmath I thought what I wanted was narrow enough. I'm looking for a study of graphs expending/unfolding the cycles of another one. What I have now is a label-preserving homomorphism of graph but I wanted to know if it was something already studied or appearing somewhere. $\endgroup$ – Boris Jun 25 at 20:18
  • $\begingroup$ The language of folding and unfolding of graphs is used by many authors, but the abundance of variations on those themes necessitates an introduction of definitions at the beginning. See for example "Folding graphs and applications, d’apr`es Stallings" by Mladen Bestvina, 2001 class notes and the helpful worked exercises by Rylee Lyman, 2019. $\endgroup$ – hardmath Jun 27 at 3:26

Your Answer

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

Browse other questions tagged or ask your own question.