{
  "id": "2206.03723",
  "version": "v1",
  "published": "2022-06-08T07:54:41.000Z",
  "updated": "2022-06-08T07:54:41.000Z",
  "title": "Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues",
  "authors": [
    "Lele Liu"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues. Let $\\lambda_1(G)$ be the largest eigenvalue of the adjacency matrix of a graph $G$, and $\\bar{G}$ be the complement of $G$. A nice conjecture states that the graph on $n$ vertices maximizing $\\lambda_1(G) + \\lambda_1(\\bar{G})$ is the join of a clique and an independent set, with $\\lfloor n/3\\rfloor$ and $\\lceil 2n/3\\rceil$ (also $\\lceil n/3\\rceil$ and $\\lfloor 2n/3\\rfloor$ if $n \\equiv 2 \\pmod{3}$) vertices, respectively. We resolve this conjecture for sufficiently large $n$ using analytic methods. Our second result concerns the $Q$-spread $s_Q(G)$ of a graph $G$, which is defined as the difference between the largest eigenvalue and least eigenvalue of the signless Laplacian of $G$. It was conjectured by Cvetkovi\\'c, Rowlinson and Simi\\'c in $2007$ that the unique $n$-vertex connected graph of maximum $Q$-spread is the graph formed by adding a pendant edge to $K_{n-1}$. We confirm this conjecture for sufficiently large $n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-06-08T07:54:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "15A18"
    ],
    "keywords": [
      "spectral graph theory",
      "linear combinations",
      "graph eigenvalues",
      "largest eigenvalue",
      "spectral extremal graph theory"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}