Maxima of the Q-index: degenerate graphs

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 $μ\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 $Δ$ and minimum degree $δ,$ 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 $Δ+1$ in which every vertex is of degree $δ$ or $Δ,$ and all other components are $δ$-regular.

No reviews yet.

No comments yet.