Partial characterization of graphs having a single large Laplacian eigenvalue

Abstract

The parameter (G) of a graph G stands for the number of Laplacian eigenvalues greater than or equal to the average degree of G. In this work, we address the problem of characterizing those graphs G having (G) = 1. Our conjecture is that these graphs are stars plus a (possible empty) set of isolated vertices. We establish a link between (G) and the number of anticomponents of G. As a by-product, we present some results which support the conjecture, by restricting our analysis to cographs, forests, and split graphs.