Rotation map

For a D-regular graph G, the rotation map ${\displaystyle \mathrm {Rot} _{G}:[N]\times [D]\rightarrow [N]\times [D]}$ is defined as follows: ${\displaystyle \mathrm {Rot} _{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.

From the definition we see that ${\displaystyle \mathrm {Rot} _{G}}$ is a permutation, and moreover ${\displaystyle \mathrm {Rot} _{G}\circ \mathrm {Rot} _{G}}$ is the identity map (${\displaystyle \mathrm {Rot} _{G}}$ is an involution).

• 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 ${\displaystyle \pi }$-consistent if ${\displaystyle \forall v\ \mathrm {Rot} _{G}(v,i)=(v[i],\pi (i))}$. From the definition, a ${\displaystyle \pi }$-consistent rotation map is consistently labeled.

• Zig-zag product
• Rotation system