rotation map

For a D-regular graph G, the rotation map $\backslash mathrm\{Rot\}\_G\; :\; [N]\; \backslash times\; [D]\; \backslash rightarrow\; [N]\; \backslash times\; [D]$ is defined as follows: $\backslash 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 $\backslash mathrm\{Rot\}\_G$ is a permutation, and moreover $\backslash mathrm\{Rot\}\_G\; \backslash circ\; \backslash mathrm\{Rot\}\_G$ is the identity map ($\backslash 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 $\backslash pi$-consistent if $\backslash forall\; v\; \backslash \; \backslash mathrm\{Rot\}\_G(v,i)=(v[i],\backslash pi\; (i))$. From the definition, a $\backslash pi$-consistent rotation map is consistently labeled.

• Zig-zag product
• Rotation system

{{Refbegin}}

• {{Cite book| first1=O. | last1=Reingold

| first2=S. | last2=Vadhan

| first3=A. | last3=Widgerson

| title=Proceedings 41st Annual Symposium on Foundations of Computer Science

| chapter=Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors

| date=2000

| doi=10.1109/SFCS.2000.892006

| pages=3–13

| arxiv=math/0406038| isbn=978-0-7695-0850-4

| s2cid=420651

}}

• {{Citation

| first=O

| last=Reingold

| title=Undirected connectivity in log-space

| journal=Journal of the ACM

| year=2008

| volume=55

| issue=4

| pages=1–24

| doi=10.1145/1391289.1391291

| s2cid=207168478

}}

• {{Citation

| first1=O. | last1=Reingold

| first2=L. | last2=Trevisan

| first3=S. | last3=Vadhan

| title=Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

| chapter=Pseudorandom walks on regular digraphs and the RL vs. L problem

| date=2006

| doi=10.1145/1132516.1132583

| pages=457–466

| isbn=978-1595931344

| s2cid=17360260

}}

• {{Citation

|first1=C. | last1=Alexander

|title=A Note on Consistent Rotation Maps of Graph Cartesian Products

|date=2021

|doi=10.13140/RG.2.2.19721.57446

}}

• {{Citation

|first1=C. | last1=Alexander

|title=Consistent Rotation Maps Induce a Unitary Shift Operator in Discrete Time Quantum Walks

|date=2021

|doi=10.13140/RG.2.2.17614.59201}}

{{Refend}}

Category:Extensions and generalizations of graphs

Category:Graph operations