کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4624564 1631626 2015 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات کاربردی
پیش نمایش صفحه اول مقاله
Orbits of rotor-router operation and stationary distribution of random walks on directed graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Applied Mathematics - Volume 70, September 2015, Pages 45–53
نویسندگان
,