1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So in some cases it is, in others it isn't? By any chance do you know what the case is for the OCR AS level maths discrete specification? $\endgroup$ – Randomer May 25 at 22:28
  • $\begingroup$ No idea, sorry. Absent data I'd guess it counts. $\endgroup$ – Ethan Bolker May 26 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.