Random walks and electrical resistances in products of graphs (Q674924)

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\).