JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 3, No 2 (1994)

William J. Martin

We study a class of highly regular t-designs. These are the subsets of vertices of the Johnson graph which are completely regular in the sense of Delsarte [2]. In [9], Meyerowitz classified the completely regular designs having strength zero. In this paper, we determine the completely regular designs having strength one and minimum distance at least two. The approach taken here utilizes the incidence matrix of ( t+1)-sets versus k-sets and is related to the representation theory of distance-regular graphs [1, 5].

1. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
2. P. Delsarte, "An algebraic approach to the association schemes of coding theory," Philips Res. Reports Suppl. 10 (1973),
3. P. Delsarte, "Hahn polynomials, discrete harmonics, and t-designs," SIAM J. Appl. Math. 34 (1978), 157-166.
4. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, London, 1993.
5. C.D. Godsil, "Bounding the diameter of distance regular graphs," Combinatorica 8 (1988), 333-343.
6. CD. Godsil and C.E. Praeger, "On completely transitive designs," preprint.
7. W.J. Martin, "Completely regular subsets," Ph.D. thesis. University of Waterloo, 1992.
8. W.J. Martin, "Completely regular designs," In preparation.
9. A.D. Meyerowitz, "Cycle-balanced partitions in distance-regular graphs," preprint.
10. A. Neumaier, "Completely regular codes," Discrete Math. 106/107 (1992), 353-360.