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 µ (H) and q (H) denote the largest eigenvalues of the adjacency matrix and the signless Laplacian of a graph H, the inequalities

µ (G) < µ (S_n,k) and q (G) < q (S_n,k)

hold, unless G = S_n,k.

The latter inequality is deduced from the following general bound, which improves some previous bounds on q (G):

If G is a graph of order n, with m edges, with maximum degree ∆ and minimum degree δ, then

q (G) ≤ min { 2∆, 1/2 ( ∆ + 2δ − 1 +√(∆ + 2δ − 1)2 + 16m − 8 (n − 1 + ∆) δ)} .

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