Maximum hitting time for random walks on graphs

DOI10.1002/rsa.3240010303zbMath0744.05044OpenAlexW1968695868MaRDI QIDQ3970909

Peter M. Winkler, Graham R. Brightwell

Publication date: 25 June 1992

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240010303

zbMATH Keywords

random walkextremal graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Paths and cycles (05C38)

Related Items (39)

Cop vs. gambler ⋮ Some further results on the maximal hitting times of trees with some given parameters ⋮ The access time of random walks on trees with given partition ⋮ Finding hitting times in various graphs ⋮ A stochastic process on a network with connections to Laplacian systems of equations ⋮ Unnamed Item ⋮ Tight inequalities among set hitting times in Markov chains ⋮ TIPSY COP AND DRUNKEN ROBBER: A VARIANT OF THE COP AND ROBBER GAME ON GRAPHS ⋮ Exact mixing times for random walks on trees ⋮ Three conjectures in extremal spectral graph theory ⋮ Containment: a variation of cops and robber ⋮ Extremal hitting times of trees with some given parameters ⋮ Walker-Breaker Games ⋮ Forest formulas of discrete Green's functions ⋮ Reversible random walks on dynamic graphs ⋮ Capturing the drunk robber on a graph ⋮ Distributed protocols against mobile eavesdroppers ⋮ A tight upper bound on the cover time for random walks on graphs ⋮ Hitting times for random walks on tricyclic graphs ⋮ Comparing eigenvector and degree dispersion with the principal ratio of a graph ⋮ Hitting times for random walks on subdivision and triangulation graphs ⋮ Lollipop and Lariat Symmetric Functions ⋮ The best mixing time for random walks on trees ⋮ A model of self‐avoiding random walks for searching complex networks ⋮ Laplace eigenvalues of graphs---a survey ⋮ The hitting and cover times of Metropolis walks ⋮ Characterizing graphs of maximum principal ratio ⋮ Slowdown for the geodesic-biased random walk ⋮ Cover time in edge-uniform stochastically-evolving graphs ⋮ The maximum relaxation time of a random walk ⋮ The hitting and cover times of random walks on finite graphs using local degree information ⋮ Chromatic posets ⋮ The hitting times of random walks on bicyclic graphs ⋮ How to Design a Linear Cover Time Random Walk on a Finite Graph ⋮ New Bounds for Edge-Cover by Random Walk ⋮ The Mixing Time of the Newman-Watts Small-World Model ⋮ The hitting time of random walk on unicyclic graphs ⋮ Unnamed Item ⋮ On the expected time for Herman's probabilistic self-stabilizing algorithm

Cites Work

• Expected hitting times for a random walk on a connected graph
• The electrical resistance of a graph captures its commute and cover times
• An introduction to covering problems for random walks on graphs

This page was built for publication: Maximum hitting time for random walks on graphs