Inverse Problems in the Theory of Distance-Regular Graphs

Abstract

For a distance-regular graph Γ of diameter 3, the graph Γ_i can be strongly regular for i = 2 or 3. Finding the parameters of Γ_i from the intersection array of Γ is a direct problem, and finding the intersection array of Γ from the parameters of Γ_i is the inverse problem. The direct and inverse problems were solved earlier by A. A. Makhnev and M. S. Nirova for i = 3. In the present paper, we solve the inverse problem for i = 2: given the parameters of a strongly regular graph Γ₂, we find the intersection array of a distance-regular graph Γ of diameter 3. It is proved that Γ₂ is not a graph in the half case. We also refine Nirova’s results on distance-regular graphs Γ of diameter 3 for which Γ₂ and Γ₃ are strongly regular. New infinite series of admissible intersection arrays are found: {r² + 3r +1, r(r +1), r + 2; 1, r + 1, r(r + 2)} for odd r divisible by 3 and {2r² + 5r + 2, r(2r + 2), 2r + 3; 1, 2r + 2, r(2r + 3)} for r indivisible by 3 and not congruent to ±1 modulo 5.