JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 10, No 1 (1999)

Edwin R. van Dam

We study (symmetric) three-class association schemes. The graphs with four distinct eigenvalues which are one of the relations of such a scheme are characterized. We also give an overview of most known constructions, and obtain necessary conditions for existence. A list of feasible parameter sets on at most 100 vertices is generated.

1. E.F. Assmus, Jr., J.A. Mezzaroba, and C.J. Salwach, “Planes and biplanes,” in Higher Combinatorics, M. Aigner (Ed.), Reidel, Dordrecht, 1977, pp. 205-212.
2. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, London, 1984.
3. H. Beker and W. Haemers, “2-Designs having an intersection number k - n,” J. Combin. Th. (A) 28 (1980), 64-81.
4. Th. Beth, D. Jungnickel, and H. Lenz, Design Theory, Wissenschaftsverlag, Mannheim, 1985.
5. N. Biggs, Algebraic Graph Theory, Cambridge University Press, Cambridge, 1974.
6. R.C. Bose and W.S. Connor, “Combinatorial properties of group divisible incomplete block designs,” Ann. Math. Statist. 23 (1952), 367-383.
7. R.C. Bose and D.M. Mesner, “On linear associative algebras corresponding to association schemes of partially balanced designs,” Ann. Math. Statist. 30 (1959), 21-38.
8. R.C. Bose and T. Shimamoto, “Classification and analysis of partially balanced incomplete block designs with two associate classes,” J. Amer. Statist. Assoc. 47 (1952), 151-184.
9. A.E. Brouwer, “Recursive constructions of mutually orthogonal Latin squares,” in Latin Squares-New De- velopments in the Theory and Applications, Ann. Discrete Math., 46 J. Dénes and A.D. Keedwell (Eds.), North-Holland, Amsterdam, 1991, pp. 149-168.
10. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, Heidelberg, 1989 (corrections and additions are available at Brouwer's homepage).
11. A.E. Brouwer, C.D. Godsil, and H.A. Wilbrink, “Isomorphisms between antipodal distance-regular graphs of diameter three,” unpublished manuscript.
12. A.E. Brouwer and W.H. Haemers, “Association schemes,” in Handbook of Combinatorics, Chap. 15, R.L. Graham, M. Grötschel, and L. Lovász (Eds.), Elsevier Science, Amsterdam, 1995.
13. A.E. Brouwer and J.H. van Lint, “Strongly regular graphs and partial geometries,” in Enumeration and Design-Proc. Silver Jubilee Conf. on Combinatorics, Waterloo, 1982, D.M. Jackson and S.A. Vanstone (Eds.), Academic Press, Toronto, 1984, pp. 85-122.
14. F.C. Bussemaker, W.H. Haemers, R. Mathon, and H.A. Wilbrink, “A (49, 16, 3, 6) strongly regular graph does not exist,” Europ. J. Combinatorics 10 (1989), 413-418.
15. F.C. Bussemaker, R.A. Mathon, and J.J. Seidel, “Tables of two-graphs,” in Combinatorics and Graph Theory, Proceedings, Calcutta, 1980, S.B. Rao (Ed.), Springer, Berlin, 1980, pp. 70-112. VAN DAM
16. D. de Caen, R. Mathon, and G.E. Moorhouse, “A family of antipodal distance-regular graphs related to the classical Preparata codes,” J. Alg. Combin. 4 (1995), 317-327.
17. A.R. Calderbank and J.-M. Goethals, “On a pair of dual subschemes of the Hamming scheme $Hn(q)$,” Europ. J. Combinatorics 6 (1985), 133-147.
18. P.J. Cameron, “On groups with several doubly transitive permutation representations,” Math. Z. 128 (1972), 1-14.
19. Y. Chang, “Imprimitive Symmetric Association Schemes of Rank 4,” Thesis, University of Michigan, 1994.
20. C.J. Colbourn and J.H. Dinitz, “Latin squares,” in The CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Eds.), CRC Press, Boca Raton, 1996, pp. 97-110 (errata are available at Dinitz' homepage).
21. M.J. Coster, “Quadratic forms in design theory,” Research Memorandum FEW 635, Tilburg University, 1994.
22. M.J. Coster and W.H. Haemers, “Quasi-symmetric designs related to the triangular graph,” Designs, Codes and Cryptography 5 (1995), 27-42.
23. E.R. van Dam, “Regular graphs with four eigenvalues,” Linear Algebra Appl. 226-228 (1995), 139-162.
24. E.R. van Dam, “Graphs with few eigenvalues-An interplay between combinatorics and algebra,” CentER dissertation series 20, Thesis, Tilburg University, 1996.
25. E.R. van Dam and W.H. Haemers, “A characterization of distance-regular graphs with diameter three,” J. Alg. Combin. 6 (1997), 299-303.
26. E.R. van Dam and E. Spence, “Small regular graphs with four eigenvalues,” Discrete Math., 189 (1998), 233-257.
27. P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Research Reports Suppl. 10 (1973).
28. R.H.F. Denniston, “Enumeration of symmetric designs (25, 9, 3),” in Algebraic and Geometric Combinatorics, Ann. Discrete Math., 15, E. Mendelsohn (Ed.), North-Holland, Amsterdam, 1982, pp. 111-127.
29. J.H. Dinitz, D.K. Garnick, and B.D. McKay, “There are 526, 915, 620 nonisomorphic one-factorizations of K12,” J. Combin. Designs 2 (1994), 273-285.
30. I.A. Farad$\check $zev, A.A. Ivanov, M.H. Klin, and A.J. Woldar (Eds.), Investigations in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht, 1994.
31. M.A. Fiol, “Some applications of the proper and adjacency polynomials in the theory of graph spectra,” Electronic J. Combinatorics 4 (1997), #R21.
32. M.A. Fiol and E. Garriga, “From local adjacency polynomials to locally pseudo-distance-regular graphs,” J. Comb. Th. (B) 71 (1997), 162-183.
33. D.G. Fon-der-Flaass, “A distance-regular graph with intersection array (5, 4, 3; 1, 1, 2) does not exist,” Europ. J. Combinatorics 14 (1993), 409-412.
34. C.D. Godsil, Algebraic Combinatorics, Chapman \& Hall, New York, 1993.
35. C.D. Godsil and A.D. Hensel, “Distance-regular covers of the complete graph,” J. Comb. Th. (B) 56 (1992), 205-238.
36. Ja.Ju. Gol'fand, A.V. Ivanov, and M.H. Klin, “Amorphic cellular rings,” in Investigations in Algebraic Theory of Combinatorial Objects, I.A. Farad$\check $zev, A.A. Ivanov, M.H. Klin, and A.J. Woldar (Eds.), Kluwer, Dordrecht, 1994, pp. 167-186.
37. W.H. Haemers, “Interlacing eigenvalues and graphs,” Linear Algebra Appl. 226-228 (1995), 593-616.
38. W.H. Haemers, “Distance-regularity and the spectrum of graphs,” Linear Algebra Appl. 236 (1996), 265-278.
39. W.H. Haemers and E. Spence, “Graphs cospectral with distance-regular graphs,” Linear Multilin. Alg. 39 (1995), 91-107.
40. W.H. Haemers and V.D. Tonchev, “Spreads in strongly regular graphs,” Designs, Codes and Cryptography 8 (1996), 145-157.
41. D.G. Higman, “Coherent algebras,” Linear Algebra Appl. 93 (1987), 209-239.
42. D.G. Higman, “Rank 4 association schemes,” unpublished manuscript.
43. S.A. Hobart, “On designs related to coherent configurations of type (2, 2; 4),” Discrete Math. 94 (1991), 103-127.
44. S.A. Hobart and W.G. Bridges, “Remarks on 2-(15, 5, 4) designs,” in Coding Theory and Design Theory, part II: Design Theory, D. Ray-Chaudhuri (Ed.), Springer, New York, 1990, pp. 132-143.
45. S.A. Hobart and S.E. Payne, “Reconstructing a generalized quadrangle from its distance two association scheme,” J. Alg. Combin. 2 (1993), 261-266.
46. A.J. Hoffman, “On the polynomial of a graph,” Amer. Math. Monthly 70 (1963), 30-36.
47. H.D.L. Hollmann, “Association schemes,” Master's Thesis, Eindhoven University of Technology, 1982.
48. H. Hollmann, “Pseudocyclic 3-class association schemes on 28 points,” Discrete Math. 52 (1984), 209-224.
49. P.W.M. John, “An extension of the triangular association scheme to three associate classes,” J. Roy. Stat. Soc. B26 (1966), 361-365.
50. A. Juri$\check $sić, “Antipodal covers,” Thesis, University of Waterloo, 1995.
51. J.H. van Lint and A. Schrijver, “Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields,” Combinatorica 1 (1981), 63-73.
52. R. Mathon, “3-Class association schemes,” Proc. Conf. Alg. Aspects Comb., Toronto 1975, Congressus Nu- merantium XIII, 1975, pp. 123-155.
53. R. Mathon, “The systems of linked 2-(16, 6, 2) designs,” Ars Comb. 11 (1981), 131-148.
54. R. Mathon and A. Rosa, “2-(v, k,$ λ$) designs of small order,” in The CRC Handbook of Combinatorial Designs, C.J. Colbourn and J.H. Dinitz (Eds.), CRC Press, Boca Raton, 1996, pp. 3-41.
55. R. Mathon and E. Spence, “On (45, 12, 3) designs,” J. Combin. Designs 4 (1996), 155-175.
56. E. Mendelsohn and A. Rosa, “One-factorizations of the complete graph-A survey,” J. Graph Th. 9 (1985), 43-65.
57. J. Ogawa, “A necessary condition for existence of regular and symmetrical experimental designs of triangular type, with partially balanced incomplete blocks,” Ann. Math. Statist. 30 (1959), 1063-1071.
58. S.E. Payne, “Coherent configurations derived from quasiregular points in generalized quadrangles,” in Finite Geometry and Combinatorics, Proc. 2nd Int. Conf. Deinze, 1992, F. de Clerck et al. (Eds.), Cambridge University Press, Cambridge, 1992, pp. 327-339.
59. H.O. Pflugfelder, Quasigroups and Loops: Introduction, Heldermann Verlag, Berlin, 199 .
60. D. Raghavarao, Construction and Combinatorial Problems in Design of Experiments, Wiley, New York, 1971.
61. D. Raghavarao and K. Chandrasekhararao, “Cubic designs,” Ann. Math. Statist. 35 (1964), 389-397.
62. J.J. Seidel, “Strongly regular graphs,” in Surveys in Combinatorics, Proc. 7th Brit. Comb. Conf., B. Bollobás (Ed.), Cambridge University Press, Cambridge, 1979, pp. 157-180.
63. S.S. Shrikhande and N.C. Jain, “The non-existence of some partially balanced incomplete block designs with latin square type association schemes,” Sankhy \?a A24 (1962), 259-268.
64. E. Spence, `Symmetric (31, 10, 3) designs with a non-trivial automorphism of odd order,” Journ. Comb. Math. and Comb. Designs 10 (1991), 51-64.
65. E. Spence, “A complete classification of symmetric (31, 10, 3) designs,” Designs, Codes and Cryptography 2 (1992), 127-136.
66. E. Spence, “Construction and classification of combinatorial designs,” in Surveys in Combinatorics, P. Rowlinson (Ed.), Cambridge University Press, Cambridge, 1995, pp. 191-213.
67. E. Spence, “Regular two-graphs on 36 vertices,” Linear Algebra Appl. 226-228 (1995), 459-498.
68. E. Spence, private communication.
69. M.N. Vartak, “On an application of Kronecker product of matrices to statistical designs,” Ann. Math. Statist. 26 (1955), 420-438.