Eulerian walks with prescribed turns
by
Arjana Žitnik
University of Ljubljana

An A-trail in an embedded graph G is a closed Eulerian walk such that every two consecutive edges lie on the boundary of a common face. When traveling along an A-trail, at each vertex we turn either left or right. To an A-trail A=(v₀, e₁, v₁, ..., e_m, v_m=v₀) we can therefore assign a sequence z₁z₂...z_m containing letters L and R in the following way: z_i=L if we turn to the left at the end of e_i when traveling along A, and z_i=D otherwise. We call this sequence the sequence of turns of the A-trail A. Conversely, given a sequence z containing letters L and R, an embedded graph G, an edge e with endvertex v, we can construct a walk with the sequence of turns z which starts at (v, e). We denote such a walk by w(v, e, z). Of course, this walk may not be Eulerian. Given an embedded graph G and a sequence of turns z we say that G is of type z if w(v, e, z) is Eulerian for any edge e and any of its endvertices v.

We give a characterization of plane Eulerian graphs which have an A-trail of a given type z. We consider also the question, which sequences of turns z allow plane Eulerian graphs of type z. We find some families of graphs of different types and some properties that such gruphs must possess. It is easy to characterize the graphs of type LRLR..., they are exactly the graphs with two orthogonal Eulerian Petrie walks. We also give a characterization of plane Eulerian graphs with minimal degree 2 which are of type LLRRLLRR....

Date received: November 28, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafp-34.