On graphs with a single large Laplacian eigenvalue

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

Marsella

Congreso; LAGOS'17 - IX Latin and American Algorithms, Graphs and Optimization; 2017

We address the problem of characterizing those graphs G having only one Laplacian eigenvalue greater than or equal to the average degree of G. Our conjecture is that these graphs are stars plus a (possible empty) set of isolated vertices.