{
  "id": "1301.3091",
  "version": "v2",
  "published": "2013-01-14T18:42:41.000Z",
  "updated": "2014-04-24T18:29:00.000Z",
  "title": "Strict inequalities for connective constants of transitive graphs",
  "authors": [
    "Geoffrey R. Grimmett",
    "Zhongyang Li"
  ],
  "comment": "To appear in Siam J Discrete Mathematics",
  "categories": [
    "math.CO",
    "math-ph",
    "math.MP",
    "math.PR"
  ],
  "abstract": "The connective constant of a graph is the exponential growth rate of the number of self-avoiding walks starting at a given vertex. Strict inequalities are proved for connective constants of vertex-transitive graphs. Firstly, the connective constant decreases strictly when the graph is replaced by a non-trivial quotient graph. Secondly, the connective constant increases strictly when a quasi-transitive family of new edges is added. These results have the following implications for Cayley graphs. The connective constant of a Cayley graph decreases strictly when a new relator is added to the group, and increases strictly when a non-trivial group element is declared to be a generator.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-04-24T18:29:00.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C30",
      "82B20",
      "60K35"
    ],
    "keywords": [
      "strict inequalities",
      "transitive graphs",
      "non-trivial group element",
      "exponential growth rate",
      "non-trivial quotient graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.3091G"
    }
  }
}