Parallelogram-Free Distance-Regular Graphs

✍ Scribed by Yuh-jeng Liang; Chih-wen Weng

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 300 KB
• Volume: 71
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1997.1787

✦ Synopsis

Let 1=(X, R) denote a distance-regular graph with distance function and diameter d 4. By a parallelogram of length i (2 i d), we mean a 4-tuple xyzu of vertices in X such that (x, y)= (z, u)=1, (x, u)=i, and (x, z)= ( y, z)= ( y, u)=i&1. We prove the following theorem. Theorem. Let 1 denote a distanceregular graph with diameter d 4, and intersection numbers a 1 =0, a 2 {0. Suppose 1 is Q-polynomial and contains no parallelograms of length 3 and no parallelograms of length 4. Then 1 has classical parameters (d, b, :, ;) with b<&1. By including results in [3], [9], we have the following corollary. Corollary. Let 1 denote a distance-regular graph with the Q-polynomial property. Suppose the diameter d 4. Then the following (i) (ii) are equivalent. (i) 1 contains no parallelograms of any length. (ii) One of the following (iia) (iic) holds. (iia) 1 is bipartite. (iib) 1 is a generalized odd graph. (iic) 1 has classical parameters (d, b, :, ;) and either b<&1 or 1 is a Hamming graph or a dual polar graph.