2013/09/19 by Vladimir Nikiforov, V. Nikiforov, Nikiforov, V.
Chemistry · Mathematics · #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Synthesis and Properties of Aromatic Compounds #math.CO #msc:05C50
paper · pdf · doi:10.48550/arxiv.1309.4837
7 pages. Version 2 corrects some mistakes
openalex publication_date 2013/09/19 · arxiv created 2014/03/23 · arxiv updated 2014/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G be a k-degenerate graph of order n. It is well-known that G has no more edges than Sn,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 Sn,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) <μ( Sn,k) and q( G) <q( Sn,k) hold, unless G=Sn,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.