×

Three-class association schemes. (English) Zbl 0929.05096

Summary: 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.

MSC:

05E30 Association schemes, strongly regular graphs
05B30 Other designs, configurations
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Assmus, E. F.; Mezzaroba, J. A.; Salwach, C. J.; Aigner, M. (ed.), Planes and biplanes, 205-212, (1977), Dordrecht · Zbl 0361.05025
[2] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin/Cummings, London, 1984. · Zbl 0555.05019
[3] Beker, H.; Haemers, W., 2-Designs having an intersection number \(k - n,\) J. Combin. Th. (A), 28, 64-81, (1980) · Zbl 0425.05009
[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] Bose, R. C.; Connor, W. S., Combinatorial properties of group divisible incomplete block designs, Ann. Math. Statist., 23, 367-383, (1952) · Zbl 0047.12902
[7] Bose, R. C.; Mesner, D. M., On linear associative algebras corresponding to association schemes of partially balanced designs, Ann. Math. Statist., 30, 21-38, (1959) · Zbl 0089.15002
[8] Bose, R. C.; Shimamoto, T., Classification and analysis of partially balanced incomplete block designs with two associate classes, J. Amer. Statist. Assoc., 47, 151-184, (1952) · Zbl 0048.11603
[9] Brouwer, A. E.; Dénes, J. (ed.); Keedwell, A. D. (ed.), Recursive constructions of mutually orthogonal Latin squares, 149-168, (1991), Amsterdam · Zbl 0742.05017
[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). · Zbl 0747.05073
[11] A.E. Brouwer, C.D. Godsil, and H.A. Wilbrink, “Isomorphisms between antipodal distance-regular graphs of diameter three,” unpublished manuscript.
[12] Brouwer, A. E.; Haemers, W. H.; Graham, R. L. (ed.); Grötschel, M. (ed.); Lovász, L. (ed.), Association schemes, (1995), Amsterdam
[13] Brouwer, A. E.; Lint, J. v.; Jackson, D. M. (ed.); Vanstone, S. A. (ed.), Strongly regular graphs and partial geometries, 85-122, (1984), Toronto
[14] Bussemaker, F. C.; Haemers, W. H.; Mathon, R.; Wilbrink, H. A., A \((49; 16; 3; 6)\) strongly regular graph does not exist, Europ. J. Combinatorics, 10, 413-418, (1989) · Zbl 0683.05024
[15] Bussemaker, F. C.; Mathon, R. A.; Seidel, J. J.; Rao, S. B. (ed.), Tables of two-graphs, 70-112, (1980), Berlin
[16] Caen, D. d.; Mathon, R.; Moorhouse, G. E., A family of antipodal distance-regular graphs related to the classical Preparata codes, J. Alg. Combin., 4, 317-327, (1995) · Zbl 0832.05100
[17] Calderbank, A. R.; Goethals, J.-M., On a pair of dual subschemes of the Hamming scheme \(H\_{}\{n\} (q),\) Europ. J. Combinatorics, 6, 133-147, (1985) · Zbl 0579.05021
[18] Cameron, P. J., On groups with several doubly transitive permutation representations, Math. Z., 128, 1-14, (1972) · Zbl 0227.20001
[19] Y. Chang, “Imprimitive Symmetric Association Schemes of Rank 4,” Thesis, University of Michigan, 1994.
[20] Colbourn, C. J.; Dinitz, J. H.; Colbourn, C. J. (ed.); Dinitz, J. H. (ed.), Latin squares, 97-110, (1996), Boca Raton · Zbl 0870.05008
[21] M.J. Coster, “Quadratic forms in design theory,” Research Memorandum FEW 635, Tilburg University, 1994.
[22] Coster, M. J.; Haemers, W. H., Quasi-symmetric designs related to the triangular graph, Designs, Codes and Cryptography, 5, 27-42, (1995) · Zbl 0815.05015
[23] Dam, E. v., Regular graphs with four eigenvalues, Linear Algebra Appl., 226-228, 139-162, (1995) · Zbl 0839.05072
[24] E.R. van Dam, “Graphs with few eigenvalues—An interplay between combinatorics and algebra,” CentER dissertation series 20, Thesis, Tilburg University, 1996.
[25] Dam, E. v.; Haemers, W. H., A characterization of distance-regular graphs with diameter three, J. Alg. Combin., 6, 299-303, (1997) · Zbl 0874.05060
[26] Dam, E. v.; Spence, E., Small regular graphs with four eigenvalues, Discrete Math., 189, 233-257, (1998) · Zbl 0956.05070
[27] P. Delsarte, “An algebraic approach to the association schemes of coding theory,” Philips Research Reports Suppl.10 (1973).
[28] Denniston, R. H.F.; Mendelsohn, E. (ed.), Enumeration of symmetric designs \((25; 9; 3), 111-127, (1982),\) Amsterdam · Zbl 0488.05011
[29] Dinitz, J. H.; Garnick, D. K.; McKay, B. D., There are 526, 915, 620 nonisomorphic one-factorizations of \(K\_{}\{12\},\) J. Combin. Designs, 2, 273-285, (1994) · Zbl 0817.05049
[30] I.A. Faradžev, A.A. Ivanov, M.H. Klin, and A.J. Woldar (Eds.), Investigations in Algebraic Theory of Combinatorial Objects, Kluwer, Dordrecht, 1994. · Zbl 0782.00025
[31] Fiol, M. A., Some applications of the proper and adjacency polynomials in the theory of graph spectra, Electronic J. Combinatorics, 4, r21, (1997) · Zbl 0885.05084
[32] Fiol, M. A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Comb. Th. (B), 71, 162-183, (1997) · Zbl 0888.05056
[33] Fon-der-Flaass, D. G., A distance-regular graph with intersection array \((5; 4; 3\) I \(1; 1; 2)\) does not exist, Europ. J. Combinatorics, 14, 409-412, (1993) · Zbl 0794.05132
[34] C.D. Godsil, Algebraic Combinatorics, Chapman & Hall, New York, 1993.
[35] Godsil, C. D.; Hensel, A. D., Distance-regular covers of the complete graph, J. Comb. Th. (B), 56, 205-238, (1992) · Zbl 0771.05031
[36] Gol, J.; Faradžzev, I. A. (ed.); Ivanov, A. A. (ed.); Klin, M. H. (ed.); Woldar, A. J. (ed.), Amorphic cellular rings, 167-186, (1994), Dordrecht · Zbl 0794.20010
[37] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616, (1995) · Zbl 0831.05044
[38] Haemers, W. H., Distance-regularity and the spectrum of graphs, Linear Algebra Appl., 236, 265-278, (1996) · Zbl 0845.05101
[39] Haemers, W. H.; Spence, E., Graphs cospectral with distance-regular graphs, Linear Multilin. Alg., 39, 91-107, (1995) · Zbl 0831.05045
[40] Haemers, W. H.; Tonchev, V. D., Spreads in strongly regular graphs, Designs, Codes and Cryptography, 8, 145-157, (1996) · Zbl 0870.05078
[41] Higman, D. G., Coherent algebras, Linear Algebra Appl., 93, 209-239, (1987) · Zbl 0618.05014
[42] D.G. Higman, “Rank 4 association schemes,” unpublished manuscript. · Zbl 0832.05099
[43] Hobart, S. A., On designs related to coherent configurations of type \((2; 2\); 4), Discrete Math., 94, 103-127, (1991) · Zbl 0756.05013
[44] Hobart, S. A.; Bridges, W. G.; Ray-Chaudhuri, D. (ed.), Remarks on \(2-(15; 5; 4)\) designs, 132-143, (1990), New York
[45] Hobart, S. A.; Payne, S. E., Reconstructing a generalized quadrangle from its distance two association scheme, J. Alg. Combin., 2, 261-266, (1993) · Zbl 0786.51006
[46] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36, (1963) · Zbl 0112.14901
[47] H.D.L. Hollmann, “Association schemes,” Master’s Thesis, Eindhoven University of Technology, 1982. · Zbl 0625.05015
[48] Hollmann, H., Pseudocyclic 3-class association schemes on 28 points, Discrete Math., 52, 209-224, (1984) · Zbl 0559.05019
[49] John, P. W.M., An extension of the triangular association scheme to three associate classes, J. Roy. Stat. Soc., B26, 361-365, (1966) · Zbl 0138.14301
[50] A. Jurišić, “Antipodal covers,” Thesis, University of Waterloo, 1995.
[51] Lint, J. v.; Schrijver, A., Construction of strongly regular graphs, two-weight codes and partial geometries by finite fields, Combinatorica, 1, 63-73, (1981) · Zbl 0491.05018
[52] Mathon, R., 3-Class association schemes, Proc. Conf. Alg. Aspects Comb., Toronto 1975, XIII, 123-155, (1975)
[53] Mathon, R., The systems of linked \(2-(16; 6; 2)\) designs, Ars Comb., 11, 131-148, (1981) · Zbl 0468.05012
[54] Mathon, R.; Rosa, A.; Colbourn, C. J. (ed.); Dinitz, J. H. (ed.), 2-(v, k, λ designs of small order, 3-41, (1996), Boca Raton
[55] Mathon, R.; Spence, E., On (45, 12, 3) designs, J. Combin. Designs, 4, 155-175, (1996) · Zbl 0912.05006
[56] Mendelsohn, E.; Rosa, A., One-factorizations of the complete graph—A survey, J. Graph Th., 9, 43-65, (1985) · Zbl 0587.05049
[57] Ogawa, J., A necessary condition for existence of regular and symmetrical experimental designs of triangular type, with partially balanced incomplete blocks, Ann. Math. Statist., 30, 1063-1071, (1959) · Zbl 0091.31601
[58] Payne, S. E.; de Clerck, F. (ed.); etal., Coherent configurations derived from quasiregular points in generalized quadrangles, 327-339, (1992), Cambridge · Zbl 0790.51006
[59] H.O. Pflugfelder, Quasigroups and Loops: Introduction, Heldermann Verlag, Berlin, 199.
[60] D. Raghavarao, Construction and Combinatorial Problems in Design of Experiments,Wiley, NewYork, 1971.
[61] Raghavarao, D.; Chandrasekhararao, K., Cubic designs, Ann. Math. Statist., 35, 389-397, (1964) · Zbl 0123.36603
[62] Seidel, J. J.; Bollobás, B. (ed.), Strongly regular graphs, 157-180, (1979), Cambridge
[63] Shrikhande, S. S.; Jain, N. C., The non-existence of some partially balanced incomplete block designs with latin square type association schemes, SankhyNa, A24, 259-268, (1962) · Zbl 0116.36604
[64] Spence, E., Symmetric (31, 10, 3) designs with a non-trivial automorphism of odd order, Journ. Comb. Math. and Comb. Designs, 10, 51-64, (1991) · Zbl 0761.05014
[65] Spence, E., A complete classification of symmetric (31, 10, 3) designs, Designs, Codes and Cryptography, 2, 127-136, (1992) · Zbl 0770.05012
[66] Spence, E.; Rowlinson, P. (ed.), Construction and classification of combinatorial designs, 191-213, (1995), Cambridge · Zbl 0842.05006
[67] Spence, E., Regular two-graphs on 36 vertices, Linear Algebra Appl., 226-228, 459-498, (1995) · Zbl 0834.05009
[68] E. Spence, private communication.
[69] Vartak, M. N., On an application of Kronecker product of matrices to statistical designs, Ann. Math. Statist., 26, 420-438, (1955) · Zbl 0065.12002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.