We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on $n$ vertices is $(1+o(1))\tfrac{54}{n^3}$. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to sharp upper …
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 …