JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 17, No 2 (2003)

Edwin R. van Dam

We study several questions about amorphic association schemes and other strongly regular decompositions of the complete graph. We investigate how two commuting edge-disjoint strongly regular graphs interact. We show that any decomposition of the complete graph into three strongly regular graphs must be an amorphic association scheme. Likewise we show that any decomposition of the complete graph into strongly regular graphs of (negative) Latin square type is an amorphic association scheme. We study strongly regular decompositions of the complete graph consisting of four graphs, and find a primitive counterexample to A.V. Ivanov”s conjecture which states that any association scheme consisting of strongly regular graphs only must be amorphic.

1. E. Bannai and T. Ito, Algebraic Combinatorics I: Association schemes, Benjamin/Cummings Publ., Menlo Park, 1984.
2. L.D. Baumert, W.H. Mills, and R.L. Ward, “Uniform cyclotomy,” J. Number. Th. 14 (1982), 67-82.
3. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Heidelberg, 1989.
4. A.E. Brouwer and J.H. van Lint, “Strongly regular graphs and partial geometries,” in Enumeration and Design, D.M. Jackson and S.A. Vanstone (Eds.), Academic Press, Toronto, 1984, pp. 85-122.
5. E.R. van Dam, “A characterization of association schemes from affine spaces,” Des. Codes Crypt. 21 (2000), 83-86.
6. E.R. van Dam, M. Klin, and M. Muzychuk, “Some implications on amorphic association schemes,” in preparation.
7. Ja.Ju. Gol'fand, A.V. Ivanov, and M. Klin, “Amorphic cellular rings,” in Investigations in Algebraic Theory of Combinatorial Objects, I.A. Farad\check zev et al. (Eds.), Kluwer, Dordrecht, 1994, pp. 167-186.
8. M. Hall Jr., “Affine generalized quadrilaterals,” in Studies in Pure Mathematics, L. Mirsky (Ed.), Academic Press, London, 1971, pp. 113-116.
9. T. Ito, A. Munemasa, and M. Yamada, “Amorphous association schemes over the Galois rings of characteristic 4,” Europ. J. Combinatorics 12 (1991), 513-526.
10. A.A. Ivanov and C.E. Praeger, “Problem session at ALCOM-91,” Europ. J. Combinatorics 15 (1994), 105- 112.
11. C.L.M. de Lange, “Some new cyclotomic strongly regular graphs,” J. Alg. Combin. 4 (1995), 329-330.
12. T.S. Michael, “The decomposition of the complete graph into three, isomorphic strongly regular graphs,” Congr. Numerantium 85 (1991), 177-183.
13. P. Rowlinson, “Certain 3-decompositions of complete graphs with an application to finite fields,” Proc. Royal Soc. Edinburgh 99A (1985), 277-281.
14. J.A. Thas, “Generalized polygons,” in Handbook of Incidence Geometry-Buildings and Foundations, F. Buekenhout (Ed.), North-Holland, Amsterdam, 1995, pp. 383-432.