Triangle- and pentagon-free distance-regular graphs with an eigenvalue multiplicity equal to the valency

Abstract

We classify triangle- and pentagon-free distance-regular graphs with diameter d >= 2, valency k, and an eigenvalue multiplicity k. In particular, we prove that such a graph is isomorphic to a cycle, a k-cube, a complete bipartite graph minus a matching, a Hadamard graph, a distance-regular graph with intersection array {k, k-1, k-c, c, 1; 1, c, k-c, k-1, k}, where k = gamma(gamma(2) + 3 gamma + 1), c = gamma(gamma + 1), gamma is an element of N, or a folded k-cube, k odd and k >= 7. This is a generalization of the results of Nomura (J. Combin. Theory Ser. B 64 (1995) 300-313) and Yamazaki (J. Combin. Theory Ser. B 66 (1996) 34-37), where they classified bipartite distance-regular graphs with an eigenvalue multiplicity k and showed that all such graphs are 2-homogeneous. We also classify bipartite almost 2-homogeneous distance-regular graphs with diameter d >=, 4. In particular, we prove that such a graph is either 2-homogeneous (and thus classified by Nomura and Yamazaki), or a folded k-cube for k even, or a generalized 2d-gon with order (1, k-1). (c) 2005 Elsevier Inc. All rights reserved.