Let G be a simple graph on n vertices with the eigenvalues (of an adjacency matrix) λ1 ≥ λ2 ≥ ... ≥ λn. For 1 ≤ i < j ≤ n, the (i,j)-spectral spread (or just (i,j)-spread) of G is defined as the difference λi - λj. The program Graffiti, developed by S. Fajtlowicz, posed the conjecture that the (1,2)-spread of fullerenes is at most 1. Here we prove this conjecture by using the interlacing theorem in an interesting manner and then extend this method to show that the dodecahedron has the largest (1,2)-spread amongst all fullerenes.
Paru en décembre 2001 , 9 pages
Ce cahier a été révisé en décembre 2003