1-Homogeneous Graphs with Cocktail Party μ-Graphs

Let Γ be a graph with diameter d ≥ 2. Recall Γ is 1-homogeneous (in the sense of Nomura) whenever for every edge xy of Γ the distance partition

is equitable and its parameters do not depend on the edge xy. Let Γ be 1-homogeneous. Then Γ is distance-regular and also locally strongly regular with parameters (v′,k′,λ′,μ′), where v′ = k, k′ = a₁, (v′ - k′ - 1)μ′ = k′(k′ - 1 - λ′) and c₂ ≥ μ′ + 1, since a μ-graph is a regular graph with valency μ′. If c₂ = μ′ + 1 and c₂ ≠ 1, then Γ is a Terwilliger graph, i.e., all the μ-graphs of Γ are complete. In [11] we classified the Terwilliger 1-homogeneous graphs with c₂ ≥ 2 and obtained that there are only three such examples. In this article we consider the case c₂ = μ′ + 2 ≥ 3, i.e., the case when the μ-graphs of Γ are the Cocktail Party graphs, and obtain that either λ′ = 0, μ′ = 2 or Γ is one of the following graphs: (i) a Johnson graph J(2m, m) with m ≥ 2, (ii) a folded Johnson graph J¯(4m, 2m) with m ≥ 3, (iii) a halved m-cube with m ≥ 4, (iv) a folded halved (2m)-cube with m ≥ 5, (v) a Cocktail Party graph K_{m × 2} with m ≥ 3, (vi) the Schläfli graph, (vii) the Gosset graph.