Counting self-avoiding walks on free products of graphs

详细信息    查看全文

• 作者：Lorenz A. Gilch^a ; ^{Lorenz.Gilch@freenet.de} ; Sebastian Mü ; ller^b ; ^{sebastian.muller@univ-amu.fr}
• 关键词：Connective constant ; Self-avoiding walk ; Free product of graphs
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：340
• 期：3
• 页码：325-332
• 全文大小：442 K
• 卷排序：340

文摘

The connective constant  μ(G)μ(G) of a graph GG is the asymptotic growth rate of the number σnσn of self-avoiding walks of length nn in GG from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that σn∼AGμ(G)nσn∼AGμ(G)n for some constant AGAG that depends on GG. In the case of products of finite graphs μ(G)μ(G) can be calculated explicitly and is shown to be an algebraic number.