Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues

arXiv2206.03723MaRDI QIDQ6401433FDOQ6401433

Authors: Lele Liu 

Publication date: 8 June 2022

Abstract: We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues. Let $lambd{a}_1(G)$ be the largest eigenvalue of the adjacency matrix of a graph $G$, and $$ be the complement of $G$. A nice conjecture states that the graph on $n$ vertices maximizing $$ is the join of a clique and an independent set, with $lfloorn/3floor$ and $lceil2n/3ceil$ (also $lceiln/3ceil$ and $lfloor2n/3floor$ if $nequiv2pmod3$) 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$.

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)

This page was built for publication: Two conjectures in spectral graph theory involving the linear combinations of graph eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401433)