Independent Sets In Association Schemes

Let X be k-regular graph on v vertices and let τ denote the least eigenvalue of its adjacency matrix A(X). If α(X) denotes the maximum size of an independent set in X, we have the following well known bound: . It is less well known that if equality holds here and S is a maximum independent set in X with characteristic vector x, then the vector is an eigenvector for A(X) with eigenvalue τ . In this paper we show how this can be used to characterise the maximal independent sets in certain classes of graphs. As a corollary we show that a graph defined on the partitions of {1, . . . ,9} with three cells of size three is a core. * Researchs upported by NSERC.