Graphs and Networks - A Walk

Question

As a walk can repeat an arc, i was wondering if it could repeat an arc consecutively and still be classed as a walk, e.g. A-B-A-C is this a walk?

Answer 1

Yes, it is a walk. A walk is a sequence of vertices $x_0,x_1,\ldots,x_k$ such that $x_i x_{i+1}$ is an edge for each $i$. There is no requirement here that the edges of the walk must be distinct.

A trail is a walk whose edges are distinct. A path is a walk whose vertices are distinct.

This is standard terminology - see [Bollobas, Modern Graph Theory, Springer GTM, 1998]. Of course, other authors could use other terminology. So the answer really depends.

Answer 2

As with many nomenclature questions about concepts that don't have long standing well recognized definitions, the answer to this one is "it depends".

In a graph theory paper or class where walks are studied the author/professor should make clear at the start whether such a sequence counts.

I think it likely that any formal definition will include this as a walk.