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
    0 references
    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

    Identifiers