Extreme values of the stationary distribution of random walks on directed graphs |
| |
Institution: | 1. Department of Mathematics, University of California, San Diego, La Jolla, CA 92093, United States;2. Center for Applied Mathematics, Tianjin University, Tianjin, 300072 China |
| |
Abstract: | We examine the stationary distribution of random walks on directed graphs. In particular, we focus on the principal ratio, which is the ratio of maximum to minimum values of vertices in the stationary distribution. We give an upper bound for this ratio over all strongly connected graphs on n vertices. We characterize all graphs achieving the upper bound and we give explicit constructions for these extremal graphs. Additionally, we show that under certain conditions, the principal ratio is tightly bounded. We also provide counterexamples to show the principal ratio cannot be tightly bounded under weaker conditions. |
| |
Keywords: | 05C20 05C50 15A18 |
本文献已被 ScienceDirect 等数据库收录! |
|