Definition:Walk (Graph Theory)
Definition
A walk on a graph is:
- an alternating series of vertices and edges
- beginning and ending with a vertex
- in which each edge is incident with the vertex immediately preceding it and the vertex immediately following it.
A walk between two vertices $u$ and $v$ is called a $u$-$v$ walk.
To describe a walk on a simple graph it is sufficient to list just the vertices in order, as the edges (being unique between vertices) are unambiguous.
Closed
A closed walk is a walk whose first vertex is the same as the last.
That is, it is a walk which ends where it starts.
Open
An open walk is a walk whose first vertex and last vertex are distinct.
That is, it is a walk which ends on a different vertex from the one where it starts.
Length
The length of a walk is the number of edges it has, counting repeated edges as many times as they appear.
A walk is said to be of infinite length if and only if it has infinitely many edges.
Also known as
Some sources refer to a walk as a path, and use the term simple path to define what we have here as a path.
Also see
- Definition:Trail: a walk in which all edges are distinct.
- Definition:Path (Graph Theory): a walk in which all vertices are distinct.
Sources
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 2.3$: Connected Graphs
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): Entry: walk
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: walk (in graph theory)