{
  "id": "2407.02535",
  "version": "v1",
  "published": "2024-07-01T19:02:48.000Z",
  "updated": "2024-07-01T19:02:48.000Z",
  "title": "Eccentricity and algebraic connectivity of graphs",
  "authors": [
    "B. Afshari",
    "M. Afshari"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph on $n$ nodes with algebraic connectivity $\\lambda_{2}$. The eccentricity of a node is defined as the length of a longest shortest path starting at that node. If $s_\\ell$ denotes the number of nodes of eccentricity at most $\\ell$, then for $\\ell \\ge 2$, $$\\lambda_{2} \\ge \\frac{ 4 \\, s_\\ell }{ (\\ell-2+\\frac{4}{n}) \\, n^2 }.$$ As a corollary, if $d$ denotes the diameter of $G$, then $$\\lambda_{2} \\ge \\frac{ 4 }{ (d-2+\\frac{4}{n}) \\, n }.$$ It is also shown that $$\\lambda_{2} \\ge \\frac{ s_\\ell }{ 1+ \\ell \\left(e(G^{\\ell})-m\\right) },$$ where $m$ and $e(G^\\ell)$ denote the number of edges in $G$ and in the $\\ell$-th power of $ G $, respectively.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-07-01T19:02:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "15A18"
    ],
    "keywords": [
      "algebraic connectivity",
      "eccentricity",
      "longest shortest path starting",
      "th power"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}