Bounding the Edge Cover Time of Random Walks on Graphs
Abstract
In recent years a great deal of attention has been focused on answering questions regarding the cover times of random walks on simple graphs. In this dissertation we answer questions about the edge cover time of such walks. We begin by reviewing many of the definitions and established results for vertex cover time. We present the little that has been published regarding bounds on the edge cover time. Having completed this review we establish a new, and sometimes more useful, global upper bound for edge cover time. We then narrow our focus and consider the edge cover time of the path. We establish an exact description of the edge cover time for a random walk on the path started at an endpoint in terms of coefficients related to the Bernoulli Numbers of the Second Kind. Studying these coefficients carefully allows us to develop a tight bound on this cover time of (n-1)sq+(Theta)(n-sq/logn). Using these results, and generalizing, provides a description of the edge cover time for walks on the path started from an arbitrary vertex. This generalization gives us a bound of (5/4)(n - 1)sq + O(n-sq/log n) for the edge cover time for the path. Having established a tight bound for walks on paths we then focus on other trees. We prove that the edge cover time for a random walk started from the center of a star graph minimizes edge cover time for walks on all trees on n vertices. We also establish the fact that in all graphs the edge cover time for a walk started from a leaf is always greater than for a walk started from its point of attachment. We continue our study of trees by establishing a global upper bound on the edge cover time for all trees and use it to study balanced k-ary trees. Finally we show the connection between our previous developments for the edge cover time for paths and that of the edge cover time on the cycle.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 03, 1996
- Accession Number
- ADA311706
Entities
People
- Eric R. Bussian
Organizations
- Air Force Institute of Technology