Independent sets in association schemes

Details Independent sets in association schemes Independent sets in association schemes

2003-11-28

arxiv.org/abs/math/0311535v2

Mathematics

Combinatorics

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

Scientific paper

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: \[ \alpha(X) \le\frac{v}{1-\frac{k}{\tau}}. \] 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.

Affiliated with

Also associated with

No associations

Rating

Independent sets in association schemes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Independent sets in association schemes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independent sets in association schemes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-309107