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).