Counting self-avoiding walks on free products of graphs

Abstract

The connective constant $\mu (G)$ of a graph $G$ is the asymptotic growth rate of the number ${\sigma }_n$ of self-avoiding walks of length $n$ in $G$ from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that ${\sigma }_n\sim A_G\mu (G{)}^n$ for some constant $A_G$ that depends on $G$. In the case of finite products $\mu (G)$ can be calculated explicitly and is shown to be an algebraic number.

10 pages