{
  "id": "1012.4856",
  "version": "v1",
  "published": "2010-12-22T01:48:52.000Z",
  "updated": "2010-12-22T01:48:52.000Z",
  "title": "Note on a relation between Randic index and algebraic connectivity",
  "authors": [
    "Xueliang Li",
    "Yongtang Shi"
  ],
  "comment": "6 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A conjecture of AutoGraphiX on the relation between the Randi\\'c index $R$ and the algebraic connectivity $a$ of a connected graph $G$ is: $$\\frac R a\\leq (\\frac{n-3+2\\sqrt{2}}{2})/(2(1- \\cos {\\frac{\\pi}{n}})) $$ with equality if and only if $G$ is $P_n$, which was proposed by Aouchiche and Hansen [M. Aouchiche and P. Hansen, A survey of automated conjectures in spectral graph theory, {\\it Linear Algebra Appl.} {\\bf 432}(2010), 2293--2322]. We prove that the conjecture holds for all trees and all connected graphs with edge connectivity $\\kappa'(G)\\geq 2$, and if $\\kappa'(G)=1$, the conjecture holds for sufficiently large $n$. The conjecture also holds for all connected graphs with diameter $D\\leq \\frac {2(n-3+2\\sqrt{2})}{\\pi^2}$ or minimum degree $\\delta\\geq \\frac n 2$. We also prove $R\\cdot a\\geq \\frac {8\\sqrt{n-1}}{nD^2}$ and $R\\cdot a\\geq \\frac {n\\delta(2\\delta-n+2)} {2(n-1)}$, and then $R\\cdot a$ is minimum for the path if $D\\leq (n-1)^{1/4}$ or $\\delta\\geq \\frac n 2-1$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-12-22T01:48:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C50",
      "05C90",
      "92E10"
    ],
    "keywords": [
      "randic index",
      "algebraic connectivity",
      "connected graph",
      "conjecture holds",
      "spectral graph theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 6,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.4856L"
    }
  }
}