A little about covering arrays, some independent sets and a graph core

Mike Newman

Abstract

Let X be the graph whose vertex set is the partitions of {1..9} into 3 cells of size 3. Vertices are adjacent when their partitions are skew, that is each cell of one partition intersects each cell of the other. More generally, we have the graphs X(n,k) whose vertex set is the partitions in {1..n} into k cells of size at least k, adjacency meaning skew.

These graphs are important because there exists an (G,k,n) covering array if and only if G maps homomorphically into X(n,k). Without even saying what a covering array is, we are motivated to ask whether X(n,k) is a core?

Using the eigenspaces of X(9,3), we can characterize all the maximum independent sets; from this it follws that X(9,3) is a core. The fact that this graph sits in an association scheme is useful, but perhaps not essential.

This leaves some interesting questions. As a byproduct, we determine that the chromatic number