Random Walks on Regular and Irregular Graphs
The DOI matches its Crossref record; 10 of the 12 references it cites were found in a registry or an index, and 2 are not checked yet.
Abstract
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 $\Theta (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 )$.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Random Walks and Electric Networks
Doyle, P., & Snell, J. (1984) · Carus Mathematical Monographs · doi:10.5948/upo9781614440222 · Cited by 1,061
Proof verification and hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267823 · Cited by 741
Random walks, universal traversal sequences, and the complexity of maze problems
Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L., & Rackoff, C. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.34 · Cited by 692
Bollobás, B. (1979) · Graduate Texts in Mathematics · doi:10.1007/978-1-4612-9967-7 · Cited by 610
The electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., & Smolensky, R. (1989) · Proceedings of the twenty-first annual ACM symposium on Theory of computing - STOC '89 · doi:10.1145/73007.73062 · Cited by 360
The electrical resistance of a graph captures its commute and cover times
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1996) · Computational Complexity · doi:10.1007/bf01270385 · Cited by 328 · cited 3×
“Alternatively, it can be bounded from above by the maximum commute time, which in turn can be bounded by 2mD, where D is the diameter of the graph, or even characterized exactly by 2mRe , where Re is the maximum e ective resistance in the graph (see [6], and also Section 3).”
BackgroundRandom walks and the effective resistance of networks
Tetali, P. (1991) · Journal of Theoretical Probability · doi:10.1007/bf01046996 · Cited by 310
Collisions Among Random Walks on a Graph
Coppersmith, D., Tetali, P., & Winkler, P. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406029 · Cited by 164
Self-citationA tight upper bound on the cover time for random walks on graphs
Feige, U. (1995) · Random Structures and Algorithms · doi:10.1002/rsa.3240060106 · Cited by 127 · cited 4×
“It was argued in [10] that this measure is preferable to dave=dmin, since it is more robust.”
BackgroundInfluentialSelf-citationMaximum hitting time for random walks on graphs
Brightwell, G., & Winkler, P. M. (1990) · Random Structures and Algorithms · doi:10.1002/rsa.3240010303 · Cited by 117 · cited 4×
“[5] G. Brightwell and P. Winkler.”
BackgroundInfluential
Research works printed but not linked: 2
- Feige Uriel, 1993, 34th Annual Symposium on Foundations of Computer Science (Palo Alto, CA, 1993), 238
- Garey M., 1979, Computers and intractability
Cited by
Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
Nedić, A., Olshevsky, A., & Shi, W. (2017) · SIAM Journal on Optimization · doi:10.1137/16m1084316 · Cited by 1,069
“• On any regular graph, δ ≤ 1 − Ω(1 /n 2 ) as a consequence of the hitting time bounds of [12]. on the • On the star graph and two-star graph (defined to be two stars on n/ 2 nodes with a connection between the centers), δ ≤ 1 − Ω(1 /n 2 ) . strategy Remark 3 ( Adapt-then-Combine and acceleration ).”
BackgroundReversible Markov Chains and Random Walks on Graphs
Aldous, D., & Fill, J. A. (2014) · Cited by 973
Chip-firing games, potential theory on graphs, and spanning trees
Baker, M. H., & Shokrieh, F. (2012) · Journal of Combinatorial Theory Series A · doi:10.1016/j.jcta.2012.07.011 · Cited by 105
Zhou, B., & Trinajstić, N. (2008) · Chemical Physics Letters · doi:10.1016/j.cplett.2008.02.060 · Cited by 91
A Reliability-Oriented Transmission Service in Wireless Sensor Networks
Liu, Y., Zhu, Y., Ni, L. M.-S., & Xue, G. (2011) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2011.113 · Cited by 76
Metadata
- Authors
- Coppersmith, D., Feige, U., & Shearer, J.
- ORCID
- Feige, Uriel
- Venue
- SIAM Journal on Discrete Mathematics
- Published
- 1996-05
- Volume
- 9
- Issue
- 2
- Pages
- 301-308
- ISSN
- 0895-4801 (ISSN-L)
- 1095-7146
- OpenAlex
- W2091147489
- Cited by
- 49
- References
- 10
- Citations by year
- 2025: 1 · 2024: 3 · 2021: 2 · 2020: 2 · 2018: 5 · 2017: 5 · 2014: 2 · 2013: 1 · 2012: 4
- FWCI
- 1.69
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Journal on Discrete Mathematics (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
- Keywords
- random walks, cover time, simple random walk, commuting time, graph structure, average degree, irregular graphs, connected graphs
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Random Walks on Regular and Irregular Graphs. https://app.cochat.ai/papers/10.1137/s0895480193260595
- The paper
- Coppersmith, D., Feige, U., & Shearer, J. (1996). Random Walks on Regular and Irregular Graphs. SIAM Journal on Discrete Mathematics. https://doi.org/10.1137/s0895480193260595
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.