𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Expected hitting times for a random walk on a connected graph

✍ Scribed by Gregory F Lawler

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
297 KB
Volume
61
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A random walk on a graph is defined in which a particle moves from one vertex to any adjoining vertex, each with equal probability. The expected number of steps to get from one point to another is considered. It is shown that the maximum expectation for a graph with N vertices is O(N3). It is also shown that for all graphs whose maximal valence is bounded by a constant K the maximum expectation is O(N2).

πŸ“œ SIMILAR VOLUMES

On k-connectivity for a geometric random
On k-connectivity for a geometric random graph
✍ Mathew D. Penrose πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 255 KB πŸ‘ 1 views

For n points uniformly randomly distributed on the unit cube in d dimensions, ## Ε½ . with dG 2, let respectively, denote the minimum r at which the graph, obtained by n n adding an edge between each pair of points distant at most r apart, is k-connected Ε½ . w x respectively, has minimum degree k

On the Mean and Variance of Cover Times
On the Mean and Variance of Cover Times for Random Walks on Graphs
✍ Frank Ball; Bruce Dunham; A Hirschowitz πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 141 KB

A method is described for calculating the mean cover time for a particle performing a simple random walk on the vertices of a finite connected graph. The method also yields the variance and generating function of the cover time. A computer program is available which utilises the approach to provide

On k-leaf connectivity of a random graph
On k-leaf connectivity of a random graph
✍ Thomasz Luczak πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 367 KB

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > f . A threshold function for k-leaf connectivity is also found. ## 1. MAIN RESULTS Let G = (V(G),E(G)) be a graph, where V (