Maxima of the Q-index: degenerate graphs

Abstract

Let $G$ be a $k$-degenerate graph of order $n.$ It is well-known that $G$has no more edges than $S_{n,k},$ the join of a complete graph of order $k$ and an independent set of order $n-k.$ In this note it is shown that $S_{n,k}$ is extremal for some spectral parameters of $G$ as well. More precisely, letting $\mu \left(H\right)$ and $q\left(H\right)$ denote the largest eigenvalues of the adjacency matrix and the signless Laplacian of a graph $H,$ the inequalities \[ μ\left( G\right) <μ\left( S_{n,k}\right) \text{ and }q\left( G\right) <q\left( S_{n,k}\right) \] hold, unless $G=S_{n,k}$. The latter inequality is deduced from the following general bound, which improves some previous bounds on $q\left(G\right)$: If $G$ is a graph of order $n$, with $m$ edges, with maximum degree $\Delta$ and minimum degree $\delta ,$ then \[ q\left( G\right) \leq\min\left\{ 2Δ,\frac{1}{2}\left( Δ+2δ-1+\sqrt{\left( Δ+2δ-1\right) ^{2}+16m-8\left( n-1+Δ\right) δ}\right) \right\} . \] Equality holds if and only if $G$ is regular or $G$ has a component of order $\Delta +1$ in which every vertex is of degree $\delta$ or $\Delta ,$ and all other components are $\delta$-regular.

7 pages. Version 2 corrects some mistakes