𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Expected hitting times for random walks on weak products of graphs

✍ Scribed by Bárbara González-Arévalo; José Luis Palacios

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
89 KB
Volume
43
Category
Article
ISSN
0167-7152

No coin nor oath required. For personal study only.

✦ Synopsis

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 product of certain unitary Cayley graphs, showing a complexity not expected from the one-dimensional results on these Cayley graphs.

📜 SIMILAR VOLUMES

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

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