Projects per year
Abstract
Let X be an infinite, locally finite, connected, quasitransitive 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 selfavoiding walks such that heights of interior vertices are bounded by the heights of the start and endvertex. The number of selfavoiding 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
 Selfavoiding walks
ASJC Scopus subject areas
 Discrete Mathematics and Combinatorics
 Theoretical Computer Science
Fields of Expertise
 Information, Communication & Computing
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., SavaHuss, 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