2003/11/28 by Chris Godsil, C. D. Godsil, Michael Newman +3 · 1 citation
Engineering · Mathematics · #05C69 #05E30 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Limits and Structures in Graph Theory #graph theory and CDMA systems #math.CO #msc:05C69 #msc:05E30
paper · pdf · doi:10.48550/arxiv.math/0311535
15 pages; This is the corrected version that will appear in Combinatorica
openalex publication_date 2003/11/28 · arxiv created 2005/03/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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: α(X) ≤\fracv1-\frackτ. 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-(|S|)/(v)\one 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.