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

Jack Koolen¹ ; Jae-Ho Lee² ; Shuang-Dong Li³ ; Yun-Han Li⁴ ; Xiaoye Liang⁴ ; Ying-Ying Tan⁴

¹University of Science and Technology of China
²University of North Florida
³Anhui University
⁴Anhui Jianzhu University

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

Let $\Gamma$ denote a distance-regular graph with diameter $D\geq 3.$ Jurišić and Vidali conjectured that if $\Gamma$ is tight with classical parameters $(D,b,\alpha,\beta)$, $b\geq 2$, then $\Gamma$ is not locally the block graph of an orthogonal array nor the block graph of a Steiner system. In the present paper, we prove this conjecture and, furthermore, extend it from the following aspect. Assume that for every triple of vertices $x, y, z$ of $\Gamma$, where $x$ and $y$ are adjacent, and $z$ is at distance $2$ from both $x$ and $y$, the number of common neighbors of $x$, $y$, $z$ is constant. We then show that if $\Gamma$ is locally the block graph of an orthogonal array (resp.~a Steiner system) with smallest eigenvalue $-m$, $m\geq 3$, then the intersection number $c_2$ is not equal to $m^2$ (resp. $m(m+1)$). Using this result, we prove that if a tight distance-regular graph $\Gamma$ is not locally the block graph of an orthogonal array or a Steiner system, then the valency (and hence diameter) of $\Gamma$ is bounded by a function in the parameter $b=b_1/(1+\theta_1)$, where $b_1$ is the intersection number of $\Gamma$ and $\theta_1$ is the second largest eigenvalue of $\Gamma$.

Détail

DOI : 10.37236/12699

Classification : 05E30, 05C12, 05C51
Mots-clés : Steiner system, block graph