Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $<v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k>$ where $v_j$'s are vertices in $G$, $e_j$'s are edges in $G$, and $e_j=v_jv_{j+1}$ for $j<k$. Suppose we add a condition that no edge is visited again in the next step itself; that is, $e_{j+1}\neq e_j$ for $1\leq j< k-2$. This is different from trail because an edge could be visited later. One could call such a walk as a no-turn-back walk. This type of walk could be of use in studying locally constrained graph homomorphisms.

Are no-turn-back walks studied in the literature?

Note: For simple graphs, the condition implies that no vertex is visited in the 'next step' itself.

  • 3
    $\begingroup$ Yes. The common term is nonbacktracking walk $\endgroup$ Jan 18 at 2:51
  • $\begingroup$ Okay, thank you. $\endgroup$ Jan 18 at 3:52


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.