Random Walks on Regular and Irregular Graphs
| Autor: | Uriel Feige, James B. Shearer, Don Coppersmith |
|---|---|
| Rok vydání: | 1996 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 9:301-308 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/s0895480193260595 |
| Popis: | For an undirected graph and an optimal cyclic list of all its vertices, the cyclic cover time is the expected time it takes a simple random walk to travel from vertex to vertex along the list until it completes a full cycle. The main result of this paper is a characterization of the cyclic cover time in terms of simple and easy-to-compute graph properties. Namely, for any connected graph, the cyclic cover time is $\Theta(n^2 d_{ave} (d^{-1})_{ave})$, where $n$ is the number of vertices in the graph, $d_{ave}$ is the average degree of its vertices, and $(d^{-1})_{ave}$ is the average of the inverse of the degree of its vertices. Other results obtained in the processes of proving the main theorem are a similar characterization of minimum resistance spanning trees of graphs, improved bounds on the cover time of graphs, and a simplified proof that the maximum commute time in any connected graph is at most $4n^3/27 + o(n^3)$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|