{
  "id": "1104.0426",
  "version": "v1",
  "published": "2011-04-03T20:29:31.000Z",
  "updated": "2011-04-03T20:29:31.000Z",
  "title": "The Randic index and the diameter of graphs",
  "authors": [
    "Yiting Yang",
    "Linyuan Lu"
  ],
  "comment": "17 pages, accepted by Discrete Mathematics",
  "doi": "10.1016/j.disc.2011.03.020",
  "categories": [
    "math.CO"
  ],
  "abstract": "The {\\it Randi\\'c index} $R(G)$ of a graph $G$ is defined as the sum of 1/\\sqrt{d_ud_v} over all edges $uv$ of $G$, where $d_u$ and $d_v$ are the degrees of vertices $u$ and $v,$ respectively. Let $D(G)$ be the diameter of $G$ when $G$ is connected. Aouchiche-Hansen-Zheng conjectured that among all connected graphs $G$ on $n$ vertices the path $P_n$ achieves the minimum values for both $R(G)/D(G)$ and $R(G)- D(G)$. We prove this conjecture completely. In fact, we prove a stronger theorem: If $G$ is a connected graph, then $R(G)-(1/2)D(G)\\geq \\sqrt{2}-1$, with equality if and only if $G$ is a path with at least three vertices.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2011-04-03T20:29:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35"
    ],
    "keywords": [
      "randic index",
      "connected graph",
      "conjecture",
      "minimum values",
      "stronger theorem"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1104.0426Y"
    }
  }
}