Random walks on regular and irregular graphs

被引：37

作者：

Coppersmith, D ^{[1
]}

Feige, U ^{[1
]}

Shearer, J ^{[1
]}

机构：

[1] WEIZMANN INST SCI, DEPT APPL MATH & COMP SCI, IL-76100 REHOVOT, ISRAEL

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1996年 / 9卷 / 02期

关键词：

random walks; graphs; electrical resistance;

D O I：

10.1137/S0895480193260595

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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

引用

页码：301 / 308

页数：8