×

zbMATH — the first resource for mathematics

Tight distance-regular graphs. (English) Zbl 0959.05121
Let \(\Gamma\) be a distance-regular graph with diameter \(d\geq 3\) and eigenvalues \(k=\theta_0>\cdots{}>\theta_d\). Then the fundamental bound is proved in Theorem 6.2: \[ \Biggl(\theta_1+\frac{k}{a_1+1}\Biggr) \Biggl(\theta_d+\frac{k}{a_1+1}\Biggr)\geq -\frac{ka_1b_1}{(a_1+1)^2}. \] We say \(\Gamma\) is tight, if \(a_1\neq 0\) and the equality holds in the fundamental bound. For eigenvalue \(\theta\) of \(\Gamma\) define the cosine sequence \(\sigma_0=1,\dots{},\sigma_d\) associated with \(\theta\) by the equalities \(c_i\sigma_{i-1}+a_i\sigma_i+b_i\sigma_{i+1}=\theta\sigma_i\) \((0\leq i\leq d)\), where \(\sigma_{-1}\) and \(\sigma_{d+1}\) are indeterminates. For each edge \(\{x,y\}\) define \(f(x,y)=a_1^{-1}|\{(z,w)\mid z,w\in \Gamma(x)\cap \Gamma(y)\) and \(\partial(z,w)=2\}|\).
Theorem 3.5. Let \(\Gamma\) be a nonbipartite distance-regular graph with diameter \(d\geq 3\) and eigenvalues \(k=\theta_0>\cdots{}>\theta_d\). Then for each edge \(\{x,y\}\), \[ b_1\frac{k+\theta_d(a_1+1)}{(k+\theta_d)(1+\theta_d)}\leq f(x,y)\leq b_1\frac{k+\theta_1(a_1+1)}{(k+\theta_1)(1+\theta_1)}. \] Some characterizations of tight graphs are obtained in terms of cosine sequences of two eigenvalues (Theorem 7.2) and auxiliary parameters (Theorem 8.3) or feasibility conditions (Theorem 9.3).
Theorem 12.6. Let \(\Gamma\) be a distance-regular graph with diameter \(d\geq 3\) and eigenvalues \(k=\theta_0>\cdots{}>\theta_d\) and let \(b^-=-1-b_1/(\theta_1+1)\), \(b^+=-1-b_1/(\theta_d+1)\). Then the following are equivalent: \((1)\) \(\Gamma\) is tight; \((2)\) for each vertex \(x\) the local graph \(\Gamma(x)\) is connected strongly regular with eigenvalues \(a_1,b^+,b^-\); \((3)\) for some vertex \(x\) the local graph \(\Gamma(x)\) is connected strongly regular with eigenvalues \(a_1,b^+,b^-\).

MSC:
05E30 Association schemes, strongly regular graphs
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin-Cummings, California, 1984. · Zbl 0555.05019
[2] A.E. Brouwer, The Soicher graph-an antipodal 3-cover of the second subconstituent of the McLaughlin graph, unpublished.
[3] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin, 1989.
[4] A.E. Brouwer, A.M. Cohen, and A. Neumaier, Corrections and additions to the book ’Distance-regular graphs’, http://www.win.tue.nl/math/dw/personalpages/aeb/drg/index.html
[5] Cameron, P. J.; Goethals, J. M.; Seidel, J. J., Strongly regular graphs having strongly regular subconstituents, J. Algebra, 55, 257-280, (1978) · Zbl 0444.05045
[6] P.J. Cameron and J.H. van Lint, London Math. Soc. Student Texts, Vol. 22: Designs, Graphs, Codes and Their Links. Cambridge Univ. Press, Cambridge, 1991. · Zbl 0743.05004
[7] Curtin, B., 2-Homogenous bipartite distance-regular graphs, Discrete Math., 187, 39-70, (1998) · Zbl 0958.05143
[8] Dickie, G. A.; Terwilliger, P. M., Dual bipartite \(Q\)-polynomial distance-regular graphs, Europ. J. Combin., 17, 613-623, (1996) · Zbl 0921.05064
[9] C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.
[10] W.H. Haemers, “Eigenvalue techniques in design and graph theory,” Ph.D. Thesis, Eindhoven University of Technology, 1979. · Zbl 0429.05012
[11] Hall, J. I., Locally Petersen graphs, J. Graph Theory, 4, 173-187, (1980) · Zbl 0407.05041
[12] A. Jurisić and J. Koolen, Krein parameters and antipodal tight graphs with diameter 3 and 4, submitted to Discrete Math. in (1999).
[13] Meixner, T., Some polar towers, Europ. J. Combin., 12, 397-415, (1991) · Zbl 0753.05016
[14] Nomura, K., Homogeneous graphs and regular near polygons, J. Combin. Theory Ser. B, 60, 63-71, (1994) · Zbl 0793.05130
[15] Nomura, K., Spin models on bipartite distance-regular graphs, J. Combin. Theory Ser. B, 64, 300-313, (1995) · Zbl 0827.05060
[16] K. Nomura, “Spin models and almost bipartite 2-homogeneous graphs,” Adv. Stud. Pure Math., 24, Math. Soc. Japan, Tokyo, 1996, pp. 285-308. Progress in algebraic combinatorics (Fukuoka, 1993). · Zbl 0858.05101
[17] Seidel, J. J.; Taylor, D. E.; Lovasz, L. (ed.); Sós, V. T. (ed.), Two-graphs, a second survey, No. 25, 689-711, (1981), Amsterdam
[18] Soicher, L. H., Three new distance-regular graphs, Europ. J. Combin., 14, 501-505, (1993) · Zbl 0794.05135
[19] Taylor, D. E., Regular 2-graphs, Proc. London Math. Soc., 35, 257-274, (1977) · Zbl 0362.05065
[20] Terwilliger, P. M., Balanced sets and \(Q\)-polynomial association schemes, Graphs Combin., 4, 87-94, (1988) · Zbl 0644.05016
[21] Terwilliger, P. M., A new inequality for distance-regular graphs, Discrete Math., 137, 319-332, (1995) · Zbl 0814.05074
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.