ELibM Journals • ELibM Home • EMIS Home • EMIS Mirrors

  EMIS Electronic Library of Mathematics (ELibM)
The Open Access Repository of Mathematics
  EMIS ELibM Electronic Journals

JOURNAL OF
ALGEBRAIC
COMBINATORICS
  Editors-in-chief: C. A. Athanasiadis, T. Lam, A. Munemasa, H. Van Maldeghem
ISSN 0925-9899 (print) • ISSN 1572-9192 (electronic)
 

Tight Distance-Regular Graphs

Aleksandar Jurišić , Jack Koolen and Paul Terwilliger

DOI: 10.1023/A:1026544111089

Abstract

We consider a distance-regular graph ( q 1 + \frac k a 1 + 1 )( q d + \frac k a 1 + 1 ) \geqslant - \frac ka 1 b 1 ( a 1 + 1) 2 . \left( {θ_1 + \frac{k}{{a_1 + 1}}} \right)\left( {θ_d + \frac{k}{{a_1 + 1}}} \right) \geqslant - \frac{{ka_1 b_1 }}{{(a_1 + 1)^2 }}.
We say Gamma is tight whenever Gamma is not bipartite, and equality holds above. We characterize the tight property in a number of ways. For example, we show Gamma is tight if and only if the intersection numbers are given by certain rational expressions involving d independent parameters. We show Gamma is tight if and only if a 1 ne 0, a d = 0, and Gamma is 1-homogeneous in the sense of Nomura. We show Gamma is tight if and only if each local graph is connected strongly-regular, with nontrivial eigenvalues -1 - b 1(1 + theta 1) -1 and -1 - b 1(1 + theta d ) -1. Three infinite families and nine sporadic examples of tight distance-regular graphs are given.

Pages: 163–197

Keywords: distance-regular graph; equality; tight graph; homogeneous; locally strongly-regular parameterization

Full Text: PDF

References

1. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin-Cummings, California, 1984.
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. P.J. Cameron, J.M. Goethals, and J.J. Seidel, “Strongly regular graphs having strongly regular subconstituents,” J. Algebra 55 (1978), 257-280.
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.
7. B. Curtin, “2-Homogenous bipartite distance-regular graphs,” Discrete Math. 187 (1998), 39-70.
8. G.A. Dickie and P.M. Terwilliger, “Dual bipartite Q-polynomial distance-regular graphs,” Europ. J. Combin. 17 (1996), 613-623.
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.
11. J.I. Hall, “Locally Petersen graphs,” J. Graph Theory 4 (1980), 173-187.
12. A. Juri\~sić and J. Koolen, Krein parameters and antipodal tight graphs with diameter 3 and 4, submitted to Discrete Math. in (1999).
13. T. Meixner, “Some polar towers,” Europ. J. Combin. 12 (1991), 397-415.
14. K. Nomura, “Homogeneous graphs and regular near polygons,” J. Combin. Theory Ser. B 60 (1994), 63-71.
15. K. Nomura, “Spin models on bipartite distance-regular graphs,” J. Combin. Theory Ser. B 64 (1995), 300-313.
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).
17. J.J. Seidel and D.E. Taylor, “Two-graphs, a second survey,” in Algebraic Methods in Graph Theory, Coll. Math. Soc. J. Bolyai 25, L. Lovasz and Vera T. Sós (Eds.), North Holland, Amsterdam, 1981, pp. 689-711.
18. L.H. Soicher, “Three new distance-regular graphs,” Europ. J. Combin. 14 (1993), 501-505.
19. D.E. Taylor, “Regular 2-graphs,” Proc. London Math. Soc. 35(3) (1977), 257-274.
20. P.M. Terwilliger, “Balanced sets and Q-polynomial association schemes,” Graphs Combin. 4 (1988), 87-94.
21. P.M. Terwilliger, “A new inequality for distance-regular graphs,” Discrete Math. 137 (1995), 319-332.



© 1992–2009 Journal of Algebraic Combinatorics
© 2012 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition