A general bridge theorem for self-avoiding walks

Christian Lindorfer

Research output: Contribution to journalArticlepeer-review

Abstract

Let X be an infinite, locally finite, connected, quasi-transitive graph without loops or multiple edges. A graph height function on X is a map adapted to the graph structure, assigning to every vertex an integer, called height. Bridges are self-avoiding walks such that heights of interior vertices are bounded by the heights of the start- and end-vertex. The number of self-avoiding walks and the number of bridges of length n starting at a vertex o of X grow exponentially in n and the bases of these growth rates are called connective constant and bridge constant, respectively. We show that for any graph height function h the connective constant of the graph is equal to the maximum of the two bridge constants given by increasing and decreasing bridges with respect to h. As a concrete example, we apply this result to calculate the connective constant of the Grandparent graph.
Original languageEnglish
Article number112092
JournalDiscrete Mathematics
Volume343
Issue number12
Early online date20 Aug 2020
DOIs
Publication statusPublished - Dec 2020

Keywords

  • Bridges
  • Grandparent graph
  • Self-avoiding walks

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Theoretical Computer Science

Fields of Expertise

  • Information, Communication & Computing

Cite this