Triangle-free distance-regular graphs

Yeh Jong Pan*, Min Hsin Lu, Chih-wen Weng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Let Γ denote a distance-regular graph with diameter d 3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that (x,y)= (z,w)=1, (x,z)=3, and (x,w)= (y,w)= (y,z)=2, where denotes the path-length distance function. Assume that Γ has intersection numbers a 1=0 and a 2 0. We prove that the following (i) and (ii) are equivalent. (i) Γ is Q-polynomial and contains no parallelograms of length 3; (ii) Γ has classical parameters (d,b,α,β) with b<-1. Furthermore, suppose that (i) and (ii) hold. We show that each of b(b+1)2(b+2)/c 2, (b-2)(b-1)b(b+1)/(2+2b-c 2) is an integer and that c 2 b(b+1). This upper bound for c 2 is optimal, since the Hermitian forms graph Her2(d) is a triangle-free distance-regular graph that satisfies c 2=b(b+1).

Original languageEnglish
Pages (from-to)23-34
Number of pages12
JournalJournal of Algebraic Combinatorics
Volume27
Issue number1
DOIs
StatePublished - 1 Feb 2008

Keywords

  • Classical parameters
  • Distance-regular graph
  • Q-polynomial

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

Cite this