On a family of highly regular graphs by Brouwer, Ivanov, and Klin

Abstract

© 2019 Elsevier B.V. Highly regular graphs for which not all regularities are explainable by symmetries are fascinating creatures. Some of them like, e.g., the line graph of W. Kantor's non-classical GQ(5 2 ,5), are stumbling stones for existing implementations of graph isomorphism tests. They appear to be extremely rare and even once constructed it is difficult to prove their high regularity. Yet some of them, like the McLaughlin graph on 275 vertices and Ivanov's graph on 256 vertices are of profound beauty. This alone makes it an attractive goal to strive for their complete classification or, failing this, at least to get a deep understanding of them. Recently, one of the authors discovered new methods for proving high regularity of graphs. Using these techniques, in this paper we study a classical family of strongly regular graphs, originally discovered by A.E. Brouwer, A.V. Ivanov, and M.H. Klin in the late 80s. We analyse their symmetries and show that they are (3,5)-regular but not 2-homogeneous. Thus we promote these graphs to the distinguished club of highly regular graphs with few symmetries.