On graphs with complete multipartite μμ-graphs

Jurišić and Koolen proposed to study 1-homogeneous distance-regular graphs, whoseμμ-graphs (that is, the graphs induced on the common neighbours of two vertices at distance 2) are complete multipartite. Examples include the Johnson graph J (8, 4), the halved 8-cube, the known generalized quadrangle of order (4, 2), an antipodal distance-regular graph constructed by T. Meixner and the Patterson graph. We investigate a more general situation, namely, requiring the graphs to have complete multipartite μμ-graphs, and that the intersection number αα exists, which means that for a triple (x,y,z)(x,y,z) of vertices in ΓΓ, such that xx and yy are adjacent and zz is at distance 2 from xx and yy, the number α(x,y,z)α(x,y,z) of common neighbours of xx, yy and zz does not depend on the choice of a triple. The latter condition is satisfied by any 1-homogeneous graph. Let Kt×nKt×n denote the complete multipartite graph with tt parts, each of which consists of an nn-coclique. We show that if ΓΓ is a graph whose μμ-graphs are all isomorphic to Kt×nKt×n and whose intersection number αα exists, then α=tα=t, as conjectured by Jurišić and Koolen, provided α≥2α≥2. We also prove t≤4t≤4, and that equality holds only when ΓΓ is the unique distance-regular graph 3.O7(3)3.O7(3).