{
  "id": "math/0012161",
  "version": "v2",
  "published": "2000-12-18T04:01:02.000Z",
  "updated": "2008-06-05T10:26:51.000Z",
  "title": "Counting Paths in Graphs",
  "authors": [
    "Laurent Bartholdi"
  ],
  "journal": "Enseign. Math. 45 (1999) 83-131",
  "categories": [
    "math.CO",
    "math.GR"
  ],
  "abstract": "We give a simple combinatorial proof of a formula that extends a result by Grigorchuk (rediscovered by Cohen) relating cogrowth and spectral radius of random walks. Our main result is an explicit equation determining the number of `bumps' on paths in a graph: in a $d$-regular (not necessarily transitive) non-oriented graph let the series $G(t)$ count all paths between two fixed points weighted by their length $t^{length}$, and $F(u,t)$ count the same paths, weighted as $u^{number of bumps}t^{length}$. Then one has $$F(1-u,t)/(1-u^2t^2) = G(t/(1+u(d-u)t^2))/(1+u(d-u)t^2).$$ We then derive the circuit series of `free products' and `direct products' of graphs. We also obtain a generalized form of the Ihara-Selberg zeta function.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-06-05T10:26:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A15",
      "05C38",
      "47A10"
    ],
    "keywords": [
      "counting paths",
      "simple combinatorial proof",
      "ihara-selberg zeta function",
      "main result",
      "explicit equation"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math.....12161B"
    }
  }
}