Title:
Euler tours and unicycles in the rotor-router model
Author:
Type:
Co-author(s) :
Abstract:
A recurrent state of the rotor-routing process on a finite sink-free graph can be represented by a unicycle that is a connected spanning subgraph containing a unique directed cycle. We distinguish between short cycles of length 2 called 'dimers' and longer ones called 'contours'. Then the rotor-router walk performing an Euler tour on the graph generates a sequence of dimers and contours which exhibits both random and regular properties. Imposing initial conditions randomly chosen from the uniform distribution we calculate expected numbers of dimers and contours and correlation between them at two successive moments of time in the sequence. On the other hand, we prove that the excess of the number of contours over dimers is an invariant depending on planarity of the subgraph but not on initial conditions. In addition, we analyze the mean-square displacement of the rotor-router walker in the recurrent state.
Date submitted:
Date accepted:
Date of publication:
DOI:
10.1088/1742-5468/2014/06/P06003
ISSN:
Language:
Journal or Publication Title:
Journal of Statistical Mechanics: Theory and Experiment
Volume:
Number:
URL:
Additional Information:
Affiliation:
Institute for Informatics and Automation Problems ; Department of Automata Theory and Applications ; Bogoliubov Laboratory of Theoretical Physics, Joint Institute for Nuclear Research