A general bridge theorem for self-avoiding walks

Christian Lindorfer

Research output: Contribution to journalArticlepeer-review


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
Issue number12
Early online date20 Aug 2020
Publication statusPublished - Dec 2020


  • 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