Universal Traversal Sequences

Anthony D'Angelo

In the late '70's while studying lower bounds on the \(s\)-\(t\)-connectivity problem, Cook presented the idea of a sequence of edge-label directions that would visit all \(n\) vertices of any connected \(d\)-regular graph regardless of the starting vertex (a universal traversal sequence). With this idea came the question of whether or not a short sequence always exists (i.e. one polynomial in \(n\)). Since then there have been few advances in its field. Aleliunas was able to prove that short sequences do always exist. I will highlight some of the findings, but I will be focusing more on results for graphs of degree 2 (i.e. cycles).