{
  "id": "1602.07039",
  "version": "v1",
  "published": "2016-02-21T03:43:52.000Z",
  "updated": "2016-02-21T03:43:52.000Z",
  "title": "Ordering connected graphs by their Kirchhoff indices",
  "authors": [
    "Kexiang Xu",
    "Kinkar Ch. Das",
    "Xiao-Dong Zhang"
  ],
  "comment": "21 pages, 3 figures, International Journal of Computer Mathematics, 2016",
  "doi": "10.1080/00207160.2015.1073722",
  "categories": [
    "math.CO"
  ],
  "abstract": "The Kirchhoff index $Kf(G)$ of a graph $G$ is the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randi\\'c. In this paper we characterized all extremal graphs with Kirchhoff index among all graphs obtained by deleting $p$ edges from a complete graph $K_n$ with $p\\leq\\lfloor\\frac{n}{2}\\rfloor$ and obtained a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order $n>27$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-21T03:43:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C12"
    ],
    "keywords": [
      "kirchhoff index",
      "ordering connected graphs",
      "ninth maximal kirchhoff indices",
      "sharp upper bound",
      "extremal graphs"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "Taylor-Francis"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160207039X"
    }
  }
}