TY - JOUR

T1 - Parallelogram-free distance-regular graphs

AU - Liang, Yuh jeng

AU - Weng, Chih-wen

PY - 1997/11/1

Y1 - 1997/11/1

N2 - LetΓ=(X,R) denote a distance-regular graph with distance function ∂ and diameterd≥4. By a parallelogram of lengthi(2≤i≤d), we mean a 4-tuplexyzuof vertices inXsuch that ∂(x,y)=∂(z,u)=1, ∂(x,u)=i, and ∂(x,z)=∂(y,z)=∂(y,u)=i-1. We prove the following theorem.THEOREM.LetGamma;denote a distance-regular graph with diameterd≥4, and intersection numbersa1=0,a2≠0. SupposeΓisQ-polynomial and contains no parallelograms of length 3 and no parallelograms of length 4. ThenΓ:has classical parameters (d,b,α,β) withb<-1. By including results in [3], [9], we have the following corollary.COROLLARY. LetGammadenote a distance-regular graph with theQ-polynomial property. Suppose the diameterd≥4. Then the following (i)-(ii) are equivalent. (i)Γcontains no parallelograms of any length. (ii) One of the following (iia)-(iic) holds. (iia)Γis bipartite. (iib)Γis a generalized odd graph. (iic)Γhas classical parameters (d,b,α,β) and eitherb<-1 orΓis a Hamming graph or a dual polar graph.

AB - LetΓ=(X,R) denote a distance-regular graph with distance function ∂ and diameterd≥4. By a parallelogram of lengthi(2≤i≤d), we mean a 4-tuplexyzuof vertices inXsuch that ∂(x,y)=∂(z,u)=1, ∂(x,u)=i, and ∂(x,z)=∂(y,z)=∂(y,u)=i-1. We prove the following theorem.THEOREM.LetGamma;denote a distance-regular graph with diameterd≥4, and intersection numbersa1=0,a2≠0. SupposeΓisQ-polynomial and contains no parallelograms of length 3 and no parallelograms of length 4. ThenΓ:has classical parameters (d,b,α,β) withb<-1. By including results in [3], [9], we have the following corollary.COROLLARY. LetGammadenote a distance-regular graph with theQ-polynomial property. Suppose the diameterd≥4. Then the following (i)-(ii) are equivalent. (i)Γcontains no parallelograms of any length. (ii) One of the following (iia)-(iic) holds. (iia)Γis bipartite. (iib)Γis a generalized odd graph. (iic)Γhas classical parameters (d,b,α,β) and eitherb<-1 orΓis a Hamming graph or a dual polar graph.

UR - http://www.scopus.com/inward/record.url?scp=0031280925&partnerID=8YFLogxK

U2 - 10.1006/jctb.1997.1787

DO - 10.1006/jctb.1997.1787

M3 - Article

AN - SCOPUS:0031280925

VL - 71

SP - 231

EP - 243

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

IS - 2

ER -