{
  "id": "1901.02047",
  "version": "v1",
  "published": "2019-01-07T20:16:20.000Z",
  "updated": "2019-01-07T20:16:20.000Z",
  "title": "Proof of a conjecture on the algebraic connectivity of a graph and its complement",
  "authors": [
    "Mostafa Einollahzadeh",
    "Mohammad Mahdi Karkhaneei"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "For a graph $G$, let $\\lambda_2(G)$ denote its second smallest Laplacian eigenvalue. It was conjectured that $\\lambda_2(G) + \\lambda_2(\\overline{G}) \\geq 1$, where $\\bar{G}$ is the complement of $G$. Here, we prove this conjecture in the general case. Also, we will show that $\\max\\{\\lambda_2(G), \\lambda_2(\\overline{G})\\} \\geq 1 - O(n^{-\\frac 13})$, where $n$ is the number of vertices of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-07T20:16:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50"
    ],
    "keywords": [
      "algebraic connectivity",
      "complement",
      "conjecture",
      "second smallest laplacian eigenvalue",
      "general case"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}