Repository logo
 

Cubic graphs and the golden mean

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

Grimmett, Geoffrey R 
Li, Zhongyang 

Abstract

The connective constant μ(G) of a graph G is the exponential growth rate of the number of self-avoiding walks starting at a given vertex. We investigate the validity of the inequality μϕ for infinite, transitive, simple, cubic graphs, where ϕ:=12(1+5) is the golden mean. The inequality is proved for several families of graphs including (i) Cayley graphs of infinite groups with three generators and strictly positive first Betti number, (ii) infinite, transitive, topologically locally finite (TLF) planar, cubic graphs, and (iii) cubic Cayley graphs with two ends. Bounds for μ are presented for transitive cubic graphs with girth either 3 or 4, and for certain quasi-transitive cubic graphs.

Description

Keywords

Self-avoiding walk, Connective constant, Cubic graph, Transitive graph, Grigorchuk group, TLF-planar graph

Journal Title

Discrete Mathematics

Conference Name

Journal ISSN

0012-365X
1872-681X

Volume Title

343

Publisher

Elsevier

Rights

All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/I03372X/1)
This work was supported in part by the Engineering and Physical Sciences Research Council under grant EP/I03372X/1. ZL acknowledges support from the Simons Foundation under grant #351813 and the National Science Foundation under grant DMS-1608896.