{
  "id": "1211.5457",
  "version": "v2",
  "published": "2012-11-23T10:08:03.000Z",
  "updated": "2012-12-07T09:16:07.000Z",
  "title": "The (revised) Szeged index and the Wiener index of a nonbipartite graph",
  "authors": [
    "Lily Chen",
    "Xueliang Li",
    "Mengmeng Liu"
  ],
  "comment": "12 pages. arXiv admin note: text overlap with arXiv:1210.6460",
  "categories": [
    "math.CO"
  ],
  "abstract": "Hansen et. al. used the computer programm AutoGraphiX to study the differences between the Szeged index $Sz(G)$ and the Wiener index $W(G)$, and between the revised Szeged index $Sz^*(G)$ and the Wiener index for a connected graph $G$. They conjectured that for a connected nonbipartite graph $G$ with $n \\geq 5$ vertices and girth $g \\geq 5,$ $ Sz(G)-W(G) \\geq 2n-5. $ Moreover, the bound is best possible as shown by the graph composed of a cycle on 5 vertices, $C_5$, and a tree $T$ on $n-4$ vertices sharing a single vertex. They also conjectured that for a connected nonbipartite graph $G$ with $n \\geq 4$ vertices, $ Sz^*(G)-W(G) \\geq \\frac{n^2+4n-6}{4}. $ Moreover, the bound is best possible as shown by the graph composed of a cycle on 3 vertices, $C_3$, and a tree $T$ on $n-3$ vertices sharing a single vertex. In this paper, we not only give confirmative proofs to these two conjectures but also characterize those graphs that achieve the two lower bounds.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-12-07T09:16:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C12",
      "05C35",
      "05C90",
      "92E10"
    ],
    "keywords": [
      "wiener index",
      "szeged index",
      "connected nonbipartite graph",
      "single vertex",
      "computer programm autographix"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1211.5457C"
    }
  }
}