𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random walks and electrical resistances in products of graphs

✍ Scribed by Béla Bollobás; Graham Brightwell

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
727 KB
Volume
73
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We study random walks and electrical resistances between pairs of vertices in products of graphs. Among the results we prove are the following. ( 1) In a graph G x P, where P is a path with endvertices x and y, and G is any graph, with vertices n and b, the resistance between vertices (a,~) and (b,c) is maximised at c' = y. ( 2) In a graph G x K,,, for vertices x and J' of the complete graph K, and a. b of the graph G, the probability that a random walk. starting from ((1.x) reaches (b,.~) before (b, J') is at least l/2.

📜 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