Distance-Regular Graphs with Valency k, Diameter D≥3 and at Most Dk+1 Vertices

Abstract

Let Γ be a distance-regular graph with valency k and diameter D ≥ 3. It has been shown that for a fixed real number α > 2, if Γ has at most αk vertices, then there are only finitely many such graphs, except for the cases where (D = 3 and Γ is imprimitive) and (D = 4 and Γ is antipodal and bipartite). And there is a classification for α ≤ 3. In this paper, we further study such distance-regular graphs for α > 3. Let β ≥ 3 be an integer, and let Γ be a distance-regular graph with valency k, diameter D ≥ 3 and at most βk + 1 vertices. Note that if D ≥ β + 1, then Γ must have at least βk + 2 vertices. Thus, the assumption that Γ has at most βk + 1 vertices implies that D ≤ β. We focus on the case where D = β and provide a classification of distance-regular graphs having at most Dk + 1 vertices.