TY - JOUR
T1 - Parallelogram-free distance-regular graphs
AU - Liang, Yuh jeng
AU - Weng, Chih-Wen
PY - 1997/11
Y1 - 1997/11
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
SN - 0095-8956
VL - 71
SP - 231
EP - 243
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -