Walk

A Walk can be imagined as an actual walk of a Traveller along the edges in a diagrammatic representation of the Graph under consideration. The traveler always walks along an Edge from one end-vertex to the other. Suppose now that we allow the traveler to change his mind when coming to the midpoint of an edge: instead of continuing along the edge towards the other end-vertex, he could return to the initial end-vertex and continue as he wishes. Then the basic constituent of a walk is no longer an edge; rather we could speak of a Walk as a Sequence of Semi-Edges. Such walks could be called semi-edge walks. A semi-edge in a walk could be followed by the other semi-edge of the same edge (thus completing the edge) or by the same semi-edge in which case the traveler returns to the vertex at which he started. A formal definition of a semi-edge walk is obtained from the above definition of a walk by deleting the word “distinct" from the description of end-vertices. Hence we have the following definition.

CVETKOVIĆ, Dragoš, ROWLINSON, Peter and SIMIĆ, Slobodan, 2009. An Introduction to the Theory of Graph Spectra. Cambridge University Press. ISBN 978-0-511-80151-8. [Accessed 5 March 2024].

See also: A Walk as a Sequence of Vertices.