Tight Distance-Regular Graphs

By Aleksandar Jurisic, J. Koolen, Paul M. Terwilliger. 2000

76 citations recorded by the source corpus.

AbstractWe consider a distance-regular graph Γ with diameter d ≥ 3 and eigenvalues k = θ0 > θ1 > ... > θd. We show the intersection numbers a1, b1 satisfy $$\left( {\theta _1 + \frac{k}{{a_1 + 1}}} \right)\left( {\theta _d + \frac{k}{{a_1 + 1}}} \right) \geqslant - \frac{{ka_1 b_1 }}{{(a_1 + 1)^2 }}.$$ We say Γ is tight whenever Γ is not bipartite, and equality holds above. We characterize the tight property in a number of ways. For example, we show Γ is tight if and only if the intersection numbers are given by certain rational expressions involving d independent parameters. We show Γ is tight if and only if a1 ≠ 0, ad = 0, and Γ is 1-homogeneous in the sense of Nomura. We show Γ is tight if and only if each local graph is connected strongly-regular, with nontrivial eigenvalues −1 − b1(1 + θ1)−1 and −1 − b1(1 + θd)−1. Three infinite families and nine sporadic examples of tight distance-regular graphs are given.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/91898270366d7231e1818fce1cae61a6a71ef620