LIÊN KẾT WEBSITE
Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
Advances in Applied Mathematics Số , năm 2015 (Tập 70, trang 45-53)
ISSN: 1968858
ISSN: 1968858
DOI: 10.1016/j.aam.2015.06.006
Tài liệu thuộc danh mục: Scopus
Article
English
Từ khóa: Graph theory; Random processes; Eulerian; Oriented spanning trees; Random Walk; Recurrent state; Rotor-router models; Spanning tree; Stationary distribution; Directed graphs
Tóm tắt tiếng anh
The rotor-router model is a popular deterministic analogue of random walk. In this paper we prove that all orbits of the rotor-router operation have the same size on a strongly connected directed graph (digraph) and give a formula for the size. By using this formula we address the following open question about orbits of the rotor-router operation: Is there an infinite family of non-Eulerian strongly connected digraphs such that the rotor-router operation on each digraph has a single orbit? It turns out that on a strongly connected digraph the stationary distribution of the simple random walk coincides with the frequency of vertices in a rotor walk. In this common aspect a rotor walk simulates a random walk. This gives one similarity between two models on (finite) digraphs. © 2015 Elsevier Inc. All rights reserved.