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 840, Taiwan

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. 359372.

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) 145157.

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), 226228, 197222.

Get the DVI | PS | PDF file of this abstract.