Counting self-avoiding walks on free products of graphs

Lorenz A. Gilch; Sebastian Müller

doi:10.1016/j.disc.2016.08.018

Counting self-avoiding walks on free products of graphs

Lorenz A. Gilch^*, Sebastian Müller

^*Corresponding author for this work

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

The connective constantμ(G) of a graph G is the asymptotic growth rate of the number σ_n of self-avoiding walks of length n in G from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that σ_n∼A_Gμ(G)ⁿ for some constant A_G that depends on G. In the case of products of finite graphs μ(G) can be calculated explicitly and is shown to be an algebraic number.

Original language	English
Pages (from-to)	325-332
Number of pages	8
Journal	Discrete Mathematics
Volume	340
Issue number	3
DOIs	https://doi.org/10.1016/j.disc.2016.08.018
Publication status	Published - 1 Mar 2017

Keywords

Connective constant
Free product of graphs
Self-avoiding walk

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2016.08.018

Cite this

@article{9b6f73c00516460cae85760efb4b62a9,

title = "Counting self-avoiding walks on free products of graphs",

abstract = "The connective constantμ(G) of a graph G is the asymptotic growth rate of the number σn of self-avoiding walks of length n in G from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that σn∼AGμ(G)n for some constant AG that depends on G. In the case of products of finite graphs μ(G) can be calculated explicitly and is shown to be an algebraic number.",

keywords = "Connective constant, Free product of graphs, Self-avoiding walk",

author = "Gilch, {Lorenz A.} and Sebastian M{\"u}ller",

year = "2017",

month = mar,

day = "1",

doi = "10.1016/j.disc.2016.08.018",

language = "English",

volume = "340",

pages = "325--332",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Counting self-avoiding walks on free products of graphs

AU - Gilch, Lorenz A.

AU - Müller, Sebastian

PY - 2017/3/1

Y1 - 2017/3/1

N2 - The connective constantμ(G) of a graph G is the asymptotic growth rate of the number σn of self-avoiding walks of length n in G from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that σn∼AGμ(G)n for some constant AG that depends on G. In the case of products of finite graphs μ(G) can be calculated explicitly and is shown to be an algebraic number.

AB - The connective constantμ(G) of a graph G is the asymptotic growth rate of the number σn of self-avoiding walks of length n in G from a given vertex. We prove a formula for the connective constant for free products of quasi-transitive graphs and show that σn∼AGμ(G)n for some constant AG that depends on G. In the case of products of finite graphs μ(G) can be calculated explicitly and is shown to be an algebraic number.

KW - Connective constant

KW - Free product of graphs

KW - Self-avoiding walk

UR - http://www.scopus.com/inward/record.url?scp=84995495666&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.08.018

DO - 10.1016/j.disc.2016.08.018

M3 - Article

AN - SCOPUS:84995495666

SN - 0012-365X

VL - 340

SP - 325

EP - 332

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 3

ER -

Counting self-avoiding walks on free products of graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this