2013/01/14 by Grimmett, Geoffrey R., Li, Zhongyang
#05C30 #60K35 #82B20 #Combinatorics (math.CO) #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR)
paper · doi:10.48550/arxiv.1301.3091
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.