A new approach to the Bipartite Fundamental Bound

• Published in: Discrete mathematics 2012-11, Vol.312 (21), p.3195-3202
• Main Author: MacLean, Mark S.
• Format: Article
• Language: English
• Subjects: Association scheme; Bipartite graph; Distance-regular graph; Eigenvalues; Graphs; Inequalities; Intersections; Mathematical analysis; Taut graph; Vector spaces; Vectors (mathematics)
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2012.07.014

We consider a bipartite distance-regular graph Γ with vertex set X, diameter D≥4, valency k≥3, and eigenvalues θ0>θ1>⋯>θD. Let CX denote the vector space over C consisting of column vectors with rows indexed by X and entries in C. For z∈X, let zˆ denote the vector in CX with a 1 in the zth row and 0 in all other rows. Fix x,y∈X with ∂(x,y)=2, where ∂ denotes the path-length distance. For 0≤i,j≤D, we define wij=∑zˆ, where the sum is over all vertices z such that ∂(x,z)=i and ∂(y,z)=j. Define a parameter Δ in terms of the intersection numbers by Δ=(b1−1)(c3−1)−(c2−1)p222. In [M. MacLean, An inequality involving two eigenvalues of a bipartite distance-regular graph, Discrete Math. 225 (2000) 193–216], we defined what it means for Γ to be taut. We show Γ is taut if and only if Δ≠0 and the vectors Exˆ,Eyˆ,Ew11,Ew22 are linearly dependent for E∈{E1,Ed}, where d=⌊D/2⌋ and Ei is the primitive idempotent associated with θi.