An upper bound on the cover time for powers of graphs

AbstractIt is shown that if G is any connected graph on n vertices, then the cover time for random walk on the Cartesian product graph Gk is at most of order d̄N(logN)2 for k=2 and at most of order d̄NlogN for k⩾3. Here d̄ is the average degree of G and N=nk. In particular N3/2(logN)2 is a general upper bound in the case k=2 and N(k+1)/klogN is a general upper bound for k⩾3. By considering the case when G is a suitable lollipop-type graph it is shown that these bounds are tight up to a constant. These results generalize known results for Znk, where Zn is the n-path