Counting self-avoiding walks on free products of graphs

Lorenz A. Gilch*, Sebastian Müller

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


The connective constantμ(G) of a graph G is the asymptotic growth rate of the number σ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 σn∼AGμ(G)n for some constant AG that depends on G. In the case of products of finite graphs μ(G) can be calculated explicitly and is shown to be an algebraic number.

Original languageEnglish
Pages (from-to)325-332
Number of pages8
JournalDiscrete Mathematics
Issue number3
Publication statusPublished - 1 Mar 2017


  • Connective constant
  • Free product of graphs
  • Self-avoiding walk

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Counting self-avoiding walks on free products of graphs'. Together they form a unique fingerprint.

Cite this