{
  "id": "1402.2995",
  "version": "v1",
  "published": "2014-02-12T22:08:12.000Z",
  "updated": "2014-02-12T22:08:12.000Z",
  "title": "Nordhaus--Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues",
  "authors": [
    "F. Ashraf",
    "B. Tayfeh-Rezaie"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph with $n$ vertices. We denote the largest signless Laplacian eigenvalue of $G$ by $q_1(G)$ and Laplacian eigenvalues of $G$ by $\\mu_1(G)\\ge\\cdots\\ge\\mu_{n-1}(G)\\ge\\mu_n(G)=0$. It is a conjecture on Laplacian spread of graphs that $\\mu_1(G)-\\mu_{n-1}(G)\\le n-1$ or equivalently $\\mu_1(G)+\\mu_1(\\Gb)\\le2n-1$. We prove the conjecture for bipartite graphs. Also we show that for any bipartite graph $G$, $\\mu_1(G)\\mu_1(\\Gb)\\le n(n-1)$. Aouchiche and Hansen [A survey of Nordhaus--Gaddum type relations, Discrete Appl. Math. 161 (2013), 466--546] conjectured that %for any graph $G$ with $n$ vertices, $q_1(G)+q_1(\\Gb)\\le3n-4$ and $q_1(G)q_1(\\Gb)\\le2n(n-2)$. We prove the former and disprove the latter by constructing a family of graphs $H_n$ where $q_1(H_n)q_1(\\ov{H_n})$ is about $2.15n^2+O(n)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-02-12T22:08:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50"
    ],
    "keywords": [
      "nordhaus-gaddum type inequalities",
      "bipartite graph",
      "largest signless laplacian eigenvalue",
      "nordhaus-gaddum type relations",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.2995A"
    }
  }
}