• Chỉ mục bởi
  • Năm xuất bản

Orbits of rotor-router operation and stationary distribution of random walks on directed graphs

Pham T.V. Institute of Mathematics, VAST, Department of Mathematics for Computer Science, 18 Hoang Quoc Viet Road, Cau Giay District, Hanoi, Viet Nam|

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



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.

Xem chi tiết