<p>Let <span class="math-container">$G$</span> be a finite undirected graph. A walk in <span class="math-container">$G$</span> is a finite sequence <span class="math-container">$&lt;v_1,e_1,v_2,e_2,\dots,v_{k-1},e_{k-1},v_k&gt;$</span> where <span class="math-container">$v_j$</span>'s are vertices in <span class="math-container">$G$</span>, <span class="math-container">$e_j$</span>'s are edges in <span class="math-container">$G$</span>, and <span class="math-container">$e_j=v_jv_{j+1}$</span> for <span class="math-container">$j&lt;k$</span>. Suppose we add a condition that <strong>no edge is visited again in the next step itself</strong>; that is, <span class="math-container">$e_{j+1}\neq e_j$</span> for <span class="math-container">$1\leq j&lt; k-2$</span>. 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.</p>
<p><em>Are no-turn-back walks studied in the literature?</em></p>
<p>Note: For simple graphs, the condition implies that no vertex is visited in the 'next step' itself.</p>

CC BY-SA 4.0
2022-01-18T02:51:44.707Z
Yes. The common term is nonbacktracking walk
Joshua Grochow
CC BY-SA 4.0
2022-01-18T03:52:32.693Z
Okay, thank you.
Cyriac Antony
<reference-request><graph-theory>
Is there a term for 'no-turn-back walk' in graph theory?
Cyriac Antony
# Is there a term for 'no-turn-back walk' in graph theory?

(Asked by: username_0 on 2022-01-18)

Let $G$ be a finite undirected graph. A walk in $G$ is a finite sequence $$ where $v\_j$'s are vertices in $G$, $e\_j$'s are edges in $G$, and $e\_j=v\_jv\_{j+1}$ for $j. 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.

**Tags:** reference-request, graph-theory
> **Comments:**
> **username_1**: Yes. The common term is nonbacktracking walk  
> **username_0**: Okay, thank you.  

---

## 0 answers

