{
  "id": "1903.04973",
  "version": "v1",
  "published": "2019-03-12T15:03:55.000Z",
  "updated": "2019-03-12T15:03:55.000Z",
  "title": "Linear algebraic techniques for spanning tree enumeration",
  "authors": [
    "Steven Klee",
    "Matthew T. Stamps"
  ],
  "comment": "This paper presents unweighted versions of the results in arXiv:1903.03575 with more concrete and concise proofs. It is intended for a broad audience and has extra emphasis on exposition. It will appear in the American Mathematical Monthly",
  "categories": [
    "math.CO"
  ],
  "abstract": "Kirchhoff's Matrix-Tree Theorem asserts that the number of spanning trees in a finite graph can be computed from the determinant of any of its reduced Laplacian matrices. In many cases, even for well-studied families of graphs, this can be computationally or algebraically taxing. We show how two well-known results from linear algebra, the Matrix Determinant Lemma and the Schur complement, can be used to elegantly count the spanning trees in several significant families of graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-03-12T15:03:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "linear algebraic techniques",
      "spanning tree enumeration",
      "kirchhoffs matrix-tree theorem asserts",
      "matrix determinant lemma",
      "significant families"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}