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 (“Entropy waves, the zig-zag graph product, and new constant-degree expanders”, 2002) in order to conveniently define the zig-zag product and prove its properties.
Given a vertex $v$ and an edge label $i$, the rotation map returns the $i$'th neighbor of $v$ and the edge label that would lead back to $v$.

Definition

For a ''D''-regular graph ''G'', the rotation map \mathrm_G : \times \rightarrow \times /math> is defined as follows: $\mathrm_G (v,i)=(w,j)$ 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 $\mathrm_G$ is a permutation, and moreover $\mathrm_G \circ \mathrm_G$ is the identity map ($\mathrm_G$ is an involution).

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 (regular) graph.
* A rotation map is $\pi$-consistent if \forall v \ \mathrm_G(v,i)=(v \pi (i)). From the definition, a $\pi$-consistent rotation map is consistently labeled.

See also

*Zig-zag product
*Rotation system

References

*

*

*

*

*
{{Refend

Extensions and generalizations of graphs
Graph operations