Distance-regular graphs with a relatively small eigenvalue multiplicity

Jack H. Koolen¹ ; Joohyung Kim² ; Jongyook Park³

¹POSTECH
²Wonkwang University
³Tilburg University

The electronic journal of combinatorics, Tome 20 (2013) no. 1

Résumé

Godsil showed that if $\Gamma$ is a distance-regular graph with diameter $D \geq 3$ and valency $k \geq 3$, and $\theta$ is an eigenvalue of $\Gamma$ with multiplicity $m \geq 2$, then $k \leq\frac{(m+2)(m-1)}{2}$.In this paper we will give a refined statement of this result. We show that if $\Gamma$ is a distance-regular graph with diameter $D \geq 3$, valency $k \geq 2$ and an eigenvalue $\theta$ with multiplicity $m\geq 2$, such that $k$ is close to $\frac{(m+2)(m-1)}{2}$, then $\theta$ must be a tail. We also characterize the distance-regular graphs with diameter $D \geq 3$, valency $k \geq 3$ and an eigenvalue $\theta$ with multiplicity $m \geq 2$ satisfying $k= \frac{(m+2)(m-1)}{2}$.

Détail

DOI : 10.37236/2410

Classification : 05E30, 05C50, 05C12
Mots-clés : distance-regular graphs, Taylor graphs, light tail, tight distance-regular graphs, small multiplicity