On the cover time of planar graphs

Details On the cover time of planar graphs On the cover time of planar graphs

2000-02-04

arxiv.org/abs/math/0002034v3

Electron.Commun.Probab.5:85-90,2000

Mathematics

Probability

To appear in Electronic Communications in Probability

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the cover time of planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the cover time of planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the cover time of planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-233093