Independent sets in association schemes

Abstract

Let $X$ be $k$-regular graph on $v$ vertices and let $\tau$ denote the least eigenvalue of its adjacency matrix $A(X)$. If $\alpha (X)$ denotes the maximum size of an independent set in $X$, we have the following well known bound: \[ α(X) \le\frac{v}{1-\frac{k}τ}. \] 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 \[ x-\frac{|S|}{v}\one \] is an eigenvector for $A(X)$ with eigenvalue $\tau$. 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.

15 pages; This is the corrected version that will appear in Combinatorica

Cited by in corpus (1)

• Colouring Lines in Projective Space