THE MAXIMUM SPECTRAL RADIUS OF GRAPHS WITH A LARGE CORE

Abstract

The (k+1)-core of a graph G, denoted by Ck+1 (G), is the subgraph obtained by repeatedly removing any vertex of degree less than or equal to k. Ck+1 (G) is the unique induced subgraph of minimum degree larger than k with a maximum number of vertices. For 1 ≤ k ≤ m ≤ n, we denote Rn,k,m = Kk ∨ (Km−k ∪ In−m). In this paper, we prove that Rn,k,m obtains the maximum spectral radius and signless Laplacian spectral radius among all n-vertex graphs whose (k + 1)-core has at most m vertices. Our result extends a recent theorem proved by Nikiforov [Electron. J. Linear Algebra, 27:250–257, 2014]. Moreover, we also present the bipartite version of our result.