Annals of Combinatorics 4 (2000) 317-326Imprimitive 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 O_{5}(3) is also included. Keywords: imprimitive association scheme, Higmanian graphs, polar graphs References 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. |