On a Conjecture of Bollobás and Brightwell Concerning Random Walks on Product Graphs

Source abstract

We consider continuous time random walks on a product graph G × H , where G is arbitrary and H consists of two vertices x and y linked by an edge. For any t >0 and any a , b ∈ V ( G ), we show that the random walk starting at ( a , x ) is more likely to have hit ( b , x ) than ( b , y ) by time t . This contrasts with the discrete time case and proves a conjecture of Bollobás and Brightwell. We also generalize the result to cases where H is either a complete graph on n vertices or a cycle on n vertices.