Tight distance-regular graphs

2001/08/29 by Aleksandar Jurisic, Jack Koolen, Paul Terwilliger
Mathematics · #math.CO #math.RA #msc:05E #msc:15A

paper · pdf

published as J. Alg. Combin. 12 (2000) 163-197 · 35 pages

arxiv created 2001/08/29 · arxiv updated 2009/11/30

Abstract

We consider a distance-regular graph \G with diameter d ≥ 3 and eigenvalues k=θ₀>θ₁>... >θ_d. We show the intersection numbers a₁, b₁ satisfy (θ₁ + k \over a₁+1) (θ_d + k \over a₁+1) ≥ - ka₁b₁ \over (a₁+1)². We say \G is \it tight whenever \G is not bipartite, and equality holds above. We characterize the tight property in a number of ways. For example, we show \G is tight if and only if the intersection numbers are given by certain rational expressions involving d independent parameters. We show \G is tight if and only if a₁\not=0, a_d=0, and \G is 1-homogeneous in the sense of Nomura. We show \G is tight if and only if each local graph is connected strongly-regular, with nontrivial eigenvalues -1-b₁(1+θ₁)^-1 and -1-b₁(1+θ_d)^-1. Three infinite families and nine sporadic examples of tight distance-regular graphs are given.

Related

• Towards a classification of 1-homogeneous distance-regular graphs with positive intersection number a₁
• A spectral characterization of strongly distance-regular graphs with diameter four
• On Distance-Regular Graphs with Smallest Eigenvalue at Least -m
• The Pseudo Cosine Sequences of a Distance-Regular Graph
• Distance-regular graphs with a few q-distance eigenvalues