Annals of Combinatorics 4 (2000) 317-326
Imprimitive Association Schemes of Low Ranks and Higmanian Graphs
Yaotsu Chang and Tayuan Huang
Department of Applied Mathematics, I-Shou University, Kaohsiung
Department of Applied Mathematics, National Chiao Tung University,
Hsinchu 30050, Taiwan
Received April 16, 1999
AMS Subject Classification: 05C30
Abstract. A natural relationship between certain strongly regular graphs, called Higmanian graphs, and certain imprimitive association schemes (isa) of rank 4 is studied. A necessary and sufficient condition for Higmanian in terms of certain partition of their vertex sets is given, followed by a necessary easy-to-check condition in terms of their parameters. As a consequence, we show among others, that a Paley graph of perfect square order is Higmanian by giving an explicit construction. As a generalization, a rank 5 fission of the polar graph O5(3) is also included.
Keywords: imprimitive association scheme, Higmanian graphs, polar graphs
1. E. Bannai and T. Ito, Algebraic Combinatorics I, Association Schemes, Benjamin/ Cummings, Menlo Park, 1984.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, 1989.
3. Y. Chang, Imprimitive symmetric rank 4 association schemes, Ph.D. Thesis, University of Michigan, August 1994.
4. A. Deza and M. Deza, The ridge graph of the metric polytope and some relatives, in: Polytopes: Abstract, Convex and Computational, T. Bisztriczky et al. Eds., Kluwer Academic, 1994, pp. 359–372.
5. M. Deza and T. Huang, A generalization of strongly regular graphs, Bulletin of the South East Asia Mathematical Society, Submitted.
6. W.H. Haemers and V.D. Tonchev, Spreads in Strongly regular graphs, Design, Codes and Cryptography 8 (1996) 145–157.
7. W. H. Haemers, Eigenvalue techniques in design and graph theory, Math. Centre Tract, Vol. 121, Mathematical Centre, Amsterdam, 1980.
8. D.G. Higman, Rank 5 association schemes and triality, linear Algebra and its Applications, (1995), 226–228, 197–222.