## Abstract

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
^{c}n(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.

Original language | English |
---|---|

Article number | #18 |

Number of pages | 52 |

Journal | Combinatorial Theory |

Volume | 3 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2023 |

## Keywords

- Cayley graph
- formal language
- multiple context free language
- Self avoiding walk
- virtually free group

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics