Triangle-free distance-regular graphs

Pan, Yeh-jong ; Lu, Min-hsin ; Weng, Chih-wen

Journal of Algebraic Combinatorics, Tome 27 (2008) no. 1, pp. 23-34.

Résumé

Summary: Let $\Gamma $ denote a distance-regular graph with diameter $d\geq 3$. By a parallelogram of length 3, we mean a 4-tuple $xyzw$ consisting of vertices of $\Gamma $ such that $\partial ( x, y)= \partial ( z, w)=1, \partial ( x, z)=3$, and $\partial ( x, w)= \partial ( y, w)= \partial ( y, z)=2$, where $\partial $ denotes the path-length distance function. Assume that $\Gamma $ has intersection numbers $a _{1}=0$ and $a _{2}\neq 0$. We prove that the following (i) and (ii) are equivalent. (i) $\Gamma $ is $Q$-polynomial and contains no parallelograms of length 3; (ii) $\Gamma $ has classical parameters $( d, b, \alpha , \beta )$ with $b - 1$. Furthermore, suppose that (i) and (ii) hold. We show that each of $b( b+1) ^{2}( b+2)/ c _{2}, ( b - 2)( b - 1) b( b+1)$/(2+$2 b - c _{2}$) is an integer and that $c _{2}\leq b( b+1)$. This upper bound for $c _{2}$ is optimal, since the Hermitian forms graph Her $_{2}( d)$ is a triangle-free distance-regular graph that satisfies $c _{2}= b( b+1)$.

Détail

Keywords: keywords distance-regular graph, $Q$-polynomial, classical parameters