On the cover time of planar graphs
| dc.creator | Jonasson, Johan | |
| dc.creator | Schramm, Oded | |
| dc.date | 2000-02-04 | |
| dc.date | 2000-05-18 | |
| dc.date.accessioned | 2026-07-07T11:44:14Z | |
| dc.date.available | 2026-07-07T11:44:14Z | |
| dc.description | The cover time of a finite connected graph is the expected number of steps needed for a simple random walk on the graph to visit all the vertices. It is known that the cover time on any n-vertex, connected graph is at least (1+o(1)) n log(n) and at most (1+o(1))(4/27)n^3. This paper proves that for bounded-degree planar graphs the cover time is at least c n(log n)^2, and at most 6n^2, where c is a positive constant depending only on the maximal degree of the graph. The lower bound is established via use of circle packings. | |
| dc.description | To appear in Electronic Communications in Probability | |
| dc.identifier | https://arxiv.org/abs/math/0002034 | |
| dc.identifier | http://arxiv.org/abs/math/0002034 | |
| dc.identifier | Electron.Commun.Probab.5:85-90,2000 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/201533 | |
| dc.subject | Probability | |
| dc.subject | 60C05; 52C26; 60J10 | |
| dc.title | On the cover time of planar graphs | |
| dc.type | text |