Independent sets in association schemes
| dc.creator | Godsil, C. D. | |
| dc.creator | Newman, M. W. | |
| dc.date | 2003-11-28 | |
| dc.date | 2005-03-15 | |
| dc.date.accessioned | 2026-07-07T05:03:23Z | |
| dc.date.available | 2026-07-07T05:03:23Z | |
| dc.description | 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) \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 $τ$. 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. | |
| dc.description | 15 pages; This is the corrected version that will appear in Combinatorica | |
| dc.identifier | https://arxiv.org/abs/math/0311535 | |
| dc.identifier | http://arxiv.org/abs/math/0311535 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/69399 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C69, 05E30 | |
| dc.title | Independent sets in association schemes | |
| dc.type | text |