TY - JOUR

T1 - On graphs with complete multipartite μ-graphs

AU - Jurišić, Aleksandar

AU - Munemasa, Akihiro

AU - Tagami, Yuki

PY - 2010/6/28

Y1 - 2010/6/28

N2 - 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) of vertices in Γ, such that x and y are adjacent and z is at distance 2 from x and y, the number α (x, y, z) of common neighbours of x, y and z does not depend on the choice of a triple. The latter condition is satisfied by any 1-homogeneous graph. Let Kt × n denote the complete multipartite graph with t parts, each of which consists of an n-coclique. We show that if Γ is a graph whose μ-graphs are all isomorphic to Kt × n and whose intersection number α exists, then α = t, as conjectured by Jurišić and Koolen, provided α ≥ 2. We also prove t ≤ 4, and that equality holds only when Γ is the unique distance-regular graph 3 . O7 (3).

AB - 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) of vertices in Γ, such that x and y are adjacent and z is at distance 2 from x and y, the number α (x, y, z) of common neighbours of x, y and z does not depend on the choice of a triple. The latter condition is satisfied by any 1-homogeneous graph. Let Kt × n denote the complete multipartite graph with t parts, each of which consists of an n-coclique. We show that if Γ is a graph whose μ-graphs are all isomorphic to Kt × n and whose intersection number α exists, then α = t, as conjectured by Jurišić and Koolen, provided α ≥ 2. We also prove t ≤ 4, and that equality holds only when Γ is the unique distance-regular graph 3 . O7 (3).

KW - μ-graph

KW - Complete multipartite graph

KW - Distance-regular graph

KW - Generalized quadrangle

KW - Local graph

KW - Regular point

UR - http://www.scopus.com/inward/record.url?scp=77950628739&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77950628739&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2009.12.009

DO - 10.1016/j.disc.2009.12.009

M3 - Article

AN - SCOPUS:77950628739

SN - 0012-365X

VL - 310

SP - 1812

EP - 1819

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -