Random walks and electrical resistances in products of graphs (Q674924)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Random walks and electrical resistances in products of graphs |
scientific article |
Statements
Random walks and electrical resistances in products of graphs (English)
0 references
16 June 1997
0 references
The authors study the behaviour of processes that take place in product graphs \(H \times G\) starting from a single vertex. Graphs are identified with electrical networks, where each edge has unit resistance. For vertices \(u\) and \(v\) of a graph, the resistance between \(u\) and \(v\) is denoted by \(R[u,v]\). Among the results are the following: (1) Let \(H\) be an arbitrary product of paths, complete graphs and cycles. Let \(x\) and \(y\) be two vertices at maximum distance in \(H\). Let \(a\) and \(b\) be distinct vertices of a graph \(G\), and consider \(G \times H\). Then \(R[(a,x),(b,v)]\) is maximised over vertices \(v\) of \(H\) at \(v = y\). (2) Let \(H\) be a graph with distinct vertices \(x\) and \(y\), and let \(G\) be a graph with distinct vertices \(a\) and \(b\). Then \[ \frac{1}{|V(H)|} \leq \frac{R_{G \times H}[(a,x),(b,y)]}{R_G[a,b]} \leq 1 + \frac{R_H[x,y]}{2}. \] Both inequalities are best possible for each fixed \(H, x,y\).
0 references
random walks
0 references
prelocation process
0 references
product graphs
0 references
electrical networks
0 references
resistance
0 references
product of paths
0 references
0 references