The maximum spectral radius of graphs with a large core

Main Article Content

Xiaocong He
Lihua Feng
Dragan Stevanović


The $(k+1)$-core of a graph $G$, denoted by $C_{k+1}(G)$, is the subgraph obtained by repeatedly removing any vertex of degree less than or equal to $k$. $C_{k+1}(G)$ is the unique induced subgraph of minimum degree larger than $k$ with a maximum number of vertices. For $1\leq k\leq m\leq n$, we denote $R_{n, k, m}=K_k\vee(K_{m-k}\cup {I_{n-m}})$. In this paper, we prove that $R_{n, 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.

Article Details