This web page contains the abstract of my paper:

"Random Walks on Regular and Irregular Graphs", with D. Coppersmith and U. Feige, Siam J. Discrete Math., 9(1996), p. 301-308.

Abstract: For an undirected graph and a 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*n*ave(d)*ave(1/d))
where n is the number of vertices in the graph, ave(d) is the average
degree of its vertices and ave(1/d) 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 (4*n**3)/27 + o(n**3).

**
[
IBM Research home page |
James B. Shearer's home page |
Up
]
**

**
[
IBM home page |
Order |
Search |
Contact IBM |
Help |
(C) |
(TM)
]
**