DIMACS TR: 2001-48
On the separator of fullerenes
Authors: Dragan Stevanovic, Gilles Caporossi
ABSTRACT
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