Rotation map

In mathematics, a rotation map is a function that represents an undirected edge-labeled graph, where each vertex enumerates its outgoing neighbors. Rotation maps were first introduced by Reingold, Vadhan and Wigderson in order to conveniently define the zig-zag product and prove its properties.
Given a vertex and an edge label, the rotation map returns the 'th neighbor of and the edge label that would lead back to.

Definition

For a D-regular graph G, the rotation map is defined as follows: if the i th edge leaving v leads to w, and the j th edge leaving w leads to v.

Basic properties

From the definition we see that is a permutation, and moreover is the identity map.

Special cases and properties

A rotation map is consistently labeled if all the edges leaving each vertex are labeled in such a way that at each vertex, the labels of the incoming edges are all distinct. Every regular graph has some consistent labeling.
A consistent rotation map can be used to encode a coined discrete time quantum walk on a graph.
A rotation map is -consistent if. From the definition, a -consistent rotation map is consistently labeled.