DIMACS TR: 2001-48

On the separator of fullerenes

Authors: Dragan Stevanovic, Gilles Caporossi


The separator of a graph is the difference between the two largest eigenvalues of its adjacency matrix. The program {\em Graffiti}, developed by S.~Fajtlowicz, posed the conjecture that the separator of any fullerene is at most~$1$. Here we prove this conjecture by using the {\it interlacing theorem} in an interesting manner and then extend this method to show that the dodecahedron has the largest separator amongst all fullerenes.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-48.ps.gz
DIMACS Home Page