Tight distance-regular graphs

Jurišić, Aleksandar ; Koolen, Jack ; Terwilliger, Paul

Journal of Algebraic Combinatorics, Tome 12 (2000) no. 2, pp. 163-197.

Résumé

Summary: We consider a distance-regular graph ( q $_{1} + \frac k a _{1} + 1$ )( q $_{ d} + \frac k a _{1} + 1 ) \geqslant - \frac ka _{1} b _{1} ( a _{1} + 1) ^{2} . \left( {\theta _1 + \frac{k}{{a_1 + 1}}} \right)\left( {\theta _d + \frac{k}{{a_1 + 1}}} \right) \geqslant $- fracka_1 b_1 (a_1 + 1)^2 . We say $Gamma$ is $tight$ whenever $Gamma$ is not bipartite, and equality holds above. We characterize the tight property in a number of ways. For example, we show $Gamma$ is tight if and only if the intersection numbers are given by certain rational expressions involving $d$ independent parameters. We show $Gamma$ is tight if and only if $a_{1} ne$ 0, $a _{d} = 0$, and $Gamma$ is 1-homogeneous in the sense of Nomura. We show $Gamma$ is tight if and only if each local graph is connected strongly-regular, with nontrivial eigenvalues -$1 - b _{1}$(1 + $theta _{1}) ^{-1}$ and -$1 - b _{1}$(1 + $theta_{ d }) ^{-1}$. Three infinite families and nine sporadic examples of tight distance-regular graphs are given.

Détail

Keywords: distance-regular graph, equality, tight graph, homogeneous, locally strongly-regular parameterization