Towards a classification of $1$-homogeneous distance-regular graphs with positive intersection number $a_1$

Abstract

Let $\Gamma$ be a graph with diameter at least two. Then $\Gamma$ is said to be $1$-homogeneous (in the sense of Nomura) whenever for every pair of adjacent vertices $x$ and $y$ in $\Gamma$, the distance partition of the vertex set of $\Gamma$ with respect to both $x$ and $y$ is equitable, and the parameters corresponding to equitable partitions are independent of the choice of $x$ and $y$. Assume that $\Gamma$ is $1$-homogeneous distance-regular with intersection number $a_1>0$ and diameter $D⩾5$. Define $b=b_1/({\theta }_1+1)$, where $b_1$ is the intersection number and ${\theta }_1$ is the second largest eigenvalue of $\Gamma$. We show that if intersection number $c_2$ is at least $2$, then $b⩾1$ and one of the following (i)--(vi) holds: (i) $\Gamma$ is a regular near $2D$-gon, (ii) $\Gamma$ is a Johnson graph $J(2D,D)$, (iii) $\Gamma$ is a halved $\ell$-cube with $\ell \in \{2D,2D+1\}$, (iv) $\Gamma$ is a folded Johnson graph $\bar{J}(4D,2D)$, (v) $\Gamma$ is a folded halved $4D$-cube, (vi) the valency of $\Gamma$ is bounded by a function of $b$. Using this result, we characterize $1$-homogeneous graphs with classical parameters and $a_1>0$, as well as tight distance-regular graphs.

arXiv comment21 pages, 1 figure

References in corpus (1)

• On the (non-)existence of tight distance-regular graphs: a local approach