Vertex-reinforced random walk on arbitrary graphs

Vertex-reinforced random walk (VRRW), defined by Pemantle, is a random proc ess in a continuously changing environment which is more likely to visit st ates it has visited before. We consider VRRW on arbitrary graphs and show t hat on almost all of them, VRRW visits only finitely many vertices with a p ositive probability. We conjecture that on all graphs of bounded degree, th is happens with probability 1, and provide a proof only for trees of this t ype. We distinguish between several different patterns of localization and expli citly describe the long-run structure of VRRW, which depends on whether a g raph contains triangles or not. While the results of this paper generalize those obtained by Pemantle and V olkov for Z(1), ideas of proofs are different and typically based on a larg e deviation principle rather than a martingale approach.