𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Expected numbers at hitting times

✍ Scribed by Colin McDiarmid

Book ID
102339031
Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
348 KB
Volume
15
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We determine exactly the expected number of hamilton cycles in the random graph obtained by starting with n isolated vertices and adding edges at random until each vertex degree is at least two. This complements recent work of Cooper and Frieze. There are similar results concerning expected numbers, for example, of perfect matchings, spanning trees, hamilton paths, and directed hamilton cycles.

πŸ“œ SIMILAR VOLUMES

Expected hitting times for random walks
Expected hitting times for random walks on weak products of graphs
✍ BΓ‘rbara GonzΓ‘lez-ArΓ©valo; JosΓ© Luis Palacios πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 89 KB

We study the symmetry properties in weak products of graphs which are inherited from the coordinate graphs and which enable the computation of expected hitting times for a random walk on the product graph. We obtain explicit values for expected hitting times between non-neighboring vertices of the p

Expected hitting times for a random walk
Expected hitting times for a random walk on a connected graph
✍ Gregory F Lawler πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 297 KB

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 s