{
  "id": "1507.08022",
  "version": "v1",
  "published": "2015-07-29T05:46:48.000Z",
  "updated": "2015-07-29T05:46:48.000Z",
  "title": "Expression for the Number of Spanning Trees of Line Graphs of Arbitrary Connected Graphs",
  "authors": [
    "Fengming Dong",
    "Weigen Yan"
  ],
  "comment": "22 pages, 7 pages, presented at the National Conference of Combinatorics and Graph Theory at Guangzhou, China in Nov. 2015. It was submitted to JGT in Feb. 2014 and revised in July 2015",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any graph $G$, let $t(G)$ be the number of spanning trees of $G$, $L(G)$ be the line graph of $G$ and for any non-negative integer $r$, $S_r(G)$ be the graph obtained from $G$ by replacing each edge $e$ by a path of length $r+1$ connecting the two ends of $e$. In this paper we find a combinatorial approach to obtain %an expression for $t(L(G))$ and more generally an expression for $t(L(S_r(G)))$. Thus we generalize some known results on the relation between $t(L(G))$ and $t(G)$ and prove a conjecture that $t(L(S_1(G)))=k^{m+s-n-1}(k+2)^{m-n+1}t(G)$ for any graph $G$ of order $n+s$ and size $m+s$ in which $s$ vertices are of degree $1$ and the others are of degree $k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-07-29T05:46:48.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "arbitrary connected graphs",
      "line graph",
      "spanning trees",
      "expression",
      "combinatorial approach"
    ],
    "tags": [
      "conference paper"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150708022D"
    }
  }
}