zbMATH — the first resource for mathematics

Nonexistence of some antipodal distance-regular graphs of diameter four. (English) Zbl 0958.05139
The authors show that for distance-regular graphs with certain intersection arrays, the first subconstituent graphs are strongly regular. Theorem 2.2. Let \(\Gamma\) be a nonbipartite distance-regular graph with diameter \(d\geq 3\), eigenvalues \(k=\theta_0>\cdots>\theta_d\), and let \(b^-=-1-b_1/(\theta_1+1)\), \(b^+=-1-b_1/(\theta_d+1)\). Then \(k(a_1+b^+b^-)\leq (a_1-b^+)(a_1-b^-)\), and equality holds if and only if all local graphs are connected strongly regular graphs with eigenvalues \(a_1,b^+,b^-\).
Let \(\Gamma\) be a distance-regular graph, whose local graphs are strongly regular with parameters \((k',\lambda',\mu')\). Then the \(\mu\)-graphs of \(\Gamma\) are regular with valency \(\mu'\), \(c_2\mu'\) is even and \(c_2\geq \mu'+1\), with equality if and only if \(\Gamma\) is a Terwilliger graph (Theorem 3.1).
Corollary 3.5. Let \(\Gamma\) be a nonbipartite antipodal distance-regular graph with diameter four and covering index \(r\) and \(k(a_1+b^+ b^-)=(a_1-b^+)(a_1-b^-)\). Then \(b^+\) and \(b^-\) are integral, \(b^+\geq 1\), \(b^-\leq -2\) and \(r\) divides \(b^+-b^-\).
Theorem 3.1 and Corollary 3.5 give new existence conditions for the corresponding distance-regular graphs. In particular 20 intersection arrays from tables of feasible parameters of nonbipartite antipodal distance-regular graphs with diameter 4 are ruled out.

05E30 Association schemes, strongly regular graphs
Full Text: DOI
[1] Biggs, N.L., Algebraic graph theory, (1974), Cambridge University Press Cambridge · Zbl 0501.05039
[2] A. E. Brouwer
[3] Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin, Heidelberg · Zbl 0747.05073
[4] A. E. Brouwer, A. M. Cohen, A. Neumaier
[5] Dickie, G.A.; Terwilliger, P.M., Dual bipartite Q -polynomial distance-regular graphs, Europ. J. combinatorics, 17, 613-623, (1996) · Zbl 0921.05064
[6] Godsil, C.D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[7] W. H. Haemers, 1979
[8] W. H. Haemers, Interlacing eigenvalues and graphs, Linear Algebr. Appl. 226, 228 · Zbl 0831.05044
[9] 1995, 593, 616
[10] Jurišić, A.; Koolen, J.; Terwilliger, P., Tight distance-regular graphs, J. algebr. comb., 12, 163-197, (2000) · Zbl 0959.05121
[11] Jurišić, A.; Koolen, J.; Terwilliger, P., Krein parameters and antipodal tight graphs with diameter 3 and 4, Discrete. math., submitted, (1999)
[12] Meixner, T., Some polar towers, Europ. J. combinatorics, 12, 397-415, (1991) · Zbl 0753.05016
[13] Soicher, L.H., Three new distance-regular graphs, Europ. J. combinatorics, 14, 501-505, (1993) · Zbl 0794.05135
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.