Triangle-free distance-regular graphs
Yeh-jong Pan
, Min-hsin Lu
and Chih-wen Weng
National Chiao Tung University Department of Applied Mathematics 1001 Ta Hsueh Road Hsinchu Taiwan 30010 Taiwan
DOI: 10.1007/s10801-007-0072-5
Abstract
Let Γ denote a distance-regular graph with diameter d\geq 3. By a parallelogram of length 3, we mean a 4-tuple xyzw consisting of vertices of Γ such that
tial ( x, y)=
tial ( z, w)=1,
tial ( x, z)=3, and
tial ( x, w)=
tial ( y, w)=
tial ( y, z)=2, where
tial denotes the path-length distance function. Assume that Γ has intersection numbers a 1=0 and a 2\neq 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+2 b - c 2) is an integer and that c 2\leq b( b+1). This upper bound for c 2 is optimal, since the Hermitian forms graph Her 2( d) is a triangle-free distance-regular graph that satisfies c 2= b( b+1).
tial ( x, y)=
tial ( z, w)=1,
tial ( x, z)=3, and
tial ( x, w)=
tial ( y, w)=
tial ( y, z)=2, where
tial denotes the path-length distance function. Assume that Γ has intersection numbers a 1=0 and a 2\neq 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+2 b - c 2) is an integer and that c 2\leq b( b+1). This upper bound for c 2 is optimal, since the Hermitian forms graph Her 2( d) is a triangle-free distance-regular graph that satisfies c 2= b( b+1).
Pages: 23–34
Keywords: keywords distance-regular graph; $Q$-polynomial; classical parameters
Full Text: PDF
References
1. Bannai, E., & Ito, T. (1984). Algebraic combinatorics I: association schemes. Menlo Park: Benjamin/Cummings.
2. Brouwer, A. E., Cohen, A. M., & Neumaier, A. (1989). Distance-regular graphs. Berlin: Springer.
3. Ivanov, A. A., & Shpectorov, S. V. (1989). Characterization of the association schemes of Hermitian forms over GF(22). Geometriae Dedicata, 30, 23-33.
4. Jurišić, A., Koolen, J., & Miklavi\check c, Š. On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency. Preprint.
5. Koolen, J. H., & Moulton, V. (2004). There are finitely many triangle-free distance-regular graphs with degree 8, 9 or
10. Journal of Algebraic Combinatorics, 19(2), 205-217.
6. Miklavi\check c, Š. (2004). Q-polynomial distance-regular graphs with a1 =
0. European Journal of Combinatorics, 25(7), 911-920.
7. Terwilliger, P. (1992). The subconstituent algebra of an association scheme (Part I). Journal of Algebraic Combinatorics, 1, 363-388.
8. Terwilliger, P. (1995). A new inequality for distance-regular graphs. Discrete Mathematics, 137, 319- 332. 9. van Lint, J. H., & Wilson, R. M. (1992). A course in combinatorics. Cambridge: Cambridge University Press.
10. Weng, C. (1995). Kite-free P - and Q-polynomial schemes. Graphs and Combinatorics, 11, 201-207.
11. Weng, C. (1997). Parallelogram-free distance-regular graphs. Journal of Combinatorial Theory, Series B, 71(2), 231-243.
12. Weng, C. (1998). Weak-geodetically closed subgraphs in distance-regular graphs. Graphs and Combinatorics, 14, 275-304.
13. Weng, C. (1999). Classical distance-regular graphs of negative type. Journal of Combinatorial Theory, Series B, 76, 93-116.
2. Brouwer, A. E., Cohen, A. M., & Neumaier, A. (1989). Distance-regular graphs. Berlin: Springer.
3. Ivanov, A. A., & Shpectorov, S. V. (1989). Characterization of the association schemes of Hermitian forms over GF(22). Geometriae Dedicata, 30, 23-33.
4. Jurišić, A., Koolen, J., & Miklavi\check c, Š. On triangle-free distance-regular graphs with an eigenvalue multiplicity equal to the valency. Preprint.
5. Koolen, J. H., & Moulton, V. (2004). There are finitely many triangle-free distance-regular graphs with degree 8, 9 or
10. Journal of Algebraic Combinatorics, 19(2), 205-217.
6. Miklavi\check c, Š. (2004). Q-polynomial distance-regular graphs with a1 =
0. European Journal of Combinatorics, 25(7), 911-920.
7. Terwilliger, P. (1992). The subconstituent algebra of an association scheme (Part I). Journal of Algebraic Combinatorics, 1, 363-388.
8. Terwilliger, P. (1995). A new inequality for distance-regular graphs. Discrete Mathematics, 137, 319- 332. 9. van Lint, J. H., & Wilson, R. M. (1992). A course in combinatorics. Cambridge: Cambridge University Press.
10. Weng, C. (1995). Kite-free P - and Q-polynomial schemes. Graphs and Combinatorics, 11, 201-207.
11. Weng, C. (1997). Parallelogram-free distance-regular graphs. Journal of Combinatorial Theory, Series B, 71(2), 231-243.
12. Weng, C. (1998). Weak-geodetically closed subgraphs in distance-regular graphs. Graphs and Combinatorics, 14, 275-304.
13. Weng, C. (1999). Classical distance-regular graphs of negative type. Journal of Combinatorial Theory, Series B, 76, 93-116.