Spectral characterization of some generalized odd graphs

Abstract

Suppose G is a connected, k-regular graph such that Spec(G) = Spec(Gamma) where Gamma is a distance-regular graph of diameter d with parameters a(1) = a(2) = ... = a(d-1) = 0 and a(d) > 0; i.e., a generalized odd graph, we show that G must be distance-regular with the same intersection array as that of Gamma in terms of the notion of Hoffman Polynomials. Furthermore, G is isomorphic to Gamma if Gamma is one of the odd polygon C2d+1 the Odd graph Od+1, the folded (2d + 1)-cube, the coset graph of binary Golay code (d = 3), the Hoffman-Singleton graph (d = 2), the Gewirtz graph (d = 2), the Higman-Sims graph (d = 2), or the second subconstituent of the Higman-Sims graph (d = 2).