Bounds on expected hitting times for a random walk on a connected graph

DOI10.1016/0024-3795(90)90321-3zbMath0711.05040OpenAlexW2071531804MaRDI QIDQ922556

José Luis Palacios

Publication date: 1990

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(90)90321-3

zbMATH Keywords

random walkconnected graphexpected hitting timesmaximum expected number of steps to get from one vertex to another

Mathematics Subject Classification ID

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

Related Items

Further results on the expected hitting time, the cover cost and the related invariants of graphs, Finding hitting times in various graphs, Hitting times for random walks on tricyclic graphs, Leontief meets Markov: sectoral vulnerabilities through circular connectivity, On some general operators of hypergraphs, The expected hitting times for finite Markov chains, Hitting times for random walks on subdivision and triangulation graphs, Laplace eigenvalues of graphs---a survey, Expected hitting times for random walks on quadrilateral graphs and their applications, Expected hitting times for random walks on the diamond hierarchical graphs involving some classical parameters, The hitting times of random walks on bicyclic graphs, Chung-Yau Invariants and Graphs with Symmetric Hitting Times, Expected hitting times for random walks on the \(k\)-triangle graph and their applications, The hitting time of random walk on unicyclic graphs, Dumbbell graphs with extremal (reverse) cover cost

Cites Work

• Unnamed Item
• Unnamed Item
• Expected hitting times for a random walk on a connected graph
• A bound on the spectral radius of graphs
• Bounds on the spectral radius of graphs with e edges
• Non-negative matrices and Markov chains. 2nd ed