Let G be a quasi-transitive, locally finite, connected graph rooted at a vertex o, and let c n (o) be the number of self-avoiding walks of length n on G starting at o. We show that if G has only thin ends, then the generating function F SAW,o (z) = ∑n⩾1 cn(o)z n is an algebraic function. In particular, the connective constant of such a graph is an algebraic number. If G is deterministically edge-labelled, that is, every (directed) edge carries a label such that no two edges starting at the same vertex have the same label, then the set of all words which can be read along the edges of self-avoiding walks starting at o forms a language denoted by L SAW,o . Assume that the group of label-preserving graph automorphisms acts quasi-transitively. We show that L SAW,o is a k-multiple context-free language if and only if the size of all ends of G is at most 2k. Applied to Cayley graphs of finitely generated groups this says that L SAW,o is multiple context-free if and only if the group is virtually free.
- Cayley graph
- formal language
- multiple context free language
- Self avoiding walk
- virtually free group
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics