Parallelogram-free distance-regular graphs

Yuh jeng Liang, Chih-wen Weng

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)231-243
Number of pages13
JournalJournal of Combinatorial Theory. Series B
Volume71
Issue number2
DOIs
StatePublished - 1 Nov 1997

Fingerprint Dive into the research topics of 'Parallelogram-free distance-regular graphs'. Together they form a unique fingerprint.

Cite this