文章基本信息

标题：On the Cover Time of Planar Graphs
本地全文：下载
作者：Jonasson, Johan ; Schramm, Oded
期刊名称：Electronic Communications in Probability
印刷版ISSN：1083-589X
出版年度：2000
卷号：5
期号：0
页码：85-90
DOI：10.1214/ECP.v5-1022
出版社：Electronic Communications in Probability
摘要：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 $\bigl(1+o(1)\bigr)n\log n$ and at most $\bigl(1+o(1)\bigr)\frac{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.
关键词：effective resistance, commute time, hitting time, difference time,circle packing, triangulation;60J10, 52C15.