Projects per year
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 language | English |
---|---|
Article number | 112092 |
Journal | Discrete Mathematics |
Volume | 343 |
Issue number | 12 |
Early online date | 20 Aug 2020 |
DOIs | |
Publication status | Published - 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
Fingerprint
Dive into the research topics of 'A general bridge theorem for self-avoiding walks'. Together they form a unique fingerprint.Projects
- 1 Active
-
Doctoral Program: Discrete Mathematics
Ebner, O., Lehner, F., Greinecker, F., Burkard, R., Wallner, J., Elsholtz, C., Woess, W., Raseta, M., Bazarova, A., Krenn, D., Lehner, F., Kang, M., Tichy, R., Sava-Huss, E., Klinz, B., Heuberger, C., Grabner, P., Barroero, F., Cuno, J., Kreso, D., Berkes, I. & Kerber, M.
1/05/10 → 30/06/24
Project: Research project