1301.3091 (Geoffrey R. Grimmett et al.)

Strict inequalities for connective constants of transitive graphs    [PDF]

Geoffrey R. Grimmett, Zhongyang Li

The connective constant of a graph is the exponential growth rate of the number of self-avoiding walks starting at a given vertex. Strict inequalities are proved for connective constants of vertex-transitive graphs. Firstly, the connective constant decreases strictly when the graph is replaced by a non-trivial quotient graph. Secondly, the connective constant increases strictly when a quasi-transitive family of new edges is added. These results have the following implications for Cayley graphs. The connective constant of a Cayley graph decreases strictly when a new relator is added to the group, and increases strictly when a non-trivial group element is declared to be a generator.

View original: http://arxiv.org/abs/1301.3091