Partial characterization of graphs having a single large Laplacian eigenvalue

ALLEM, L. EMILIO; CAFURE, ANTONIO; DRATMAN, EZEQUIEL; GRIPPO, LUCIANO N.; SAFE, MARTÍN D.; TREVISAN, VILMAR

ELECTRONIC JOURNAL OF COMBINATORICS, THE

ELECTRONIC JOURNAL OF COMBINATORICS

Año: 2018 vol. 25 p. 1 - 10

1077-8926

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.