<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
An Improvement of the Godsil Bound
Akira Hiraki1 and Jack Koolen2
1Division of Mathematical Sciences, Osaka Kyoiku University, Kashiwara, Osaka 582-8582, Japan
hiraki@ikoma.cc.osaka-kyoiku.ac.jp
2Graduate School of Mathematics, Kyushu University, Fukuoka, 812-8581, Japan
jack@math.kyushu-u.ac.jp
Annals of Combinatorics 6 (1) p.33-44 March, 2002
AMS Subject Classification: 05Exx
Abstract:
In 1988, Godsil [12] showed that for a distance-regular graph with valency k and an eigenvalue with multiplicity the diameter d is bounded by 3m-4. In this note, we show that . Furthermore, we show that if the numerical girth is at least 6, then . Finally, we show that if the numerical girth is at least 12 then kd < 48m.
Keywords: distance-regular graph, diameter, multiplicity

References:

1. E. Bannai and T. Ito, Algebraic Combinatorics I: Association Schemes, Benjamin- Cummings Lecture Note Ser. 58, Benjamin/Cummings Publ. Co., London, 1984.

2. N.L. Biggs, Algebraic Graph Theory, Cambridge Tracts in Math. 67, Cambridge Univ. Press, 1974.

3. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer, Heidelberg, 1989.

4. C.D. Godsil, Algebraic Combinatorics, Chapman and Hall, New York, 1993.

5. J.H. Koolen, Euclidean representations and substructures of distance-regular graphs, Ph.D. Thesis, Eindhoven University of Technology, 1994.

6. E. Bannai and T. Ito, On distance-regular graphs with fixed valency, Graphs and Combin. 3 (1987) 95每109.

7. N.L. Biggs, A.G. Boshier, and J. Shawe-Taylor, Cubic distance-regular graphs, J. London Math. Soc. 33 (2) (1986) 385每394.

8. A. Boshier and K. Nomura, A remark on the intersection arrays of distance-regular graphs, J. Combin. Theory Ser. B 44 (1988) 147每153.

9. A.E. Brouwer and J.H. Koolen, The distance-regular graphs of valency four, J. Algebraic Combin. 10 (1999) 5每24.

10. Y.L. Chen and A. Hiraki, On the non-existence of certain distance-regular graphs, Kyushu J. Math. 53 (1999) 1每15.

11. Y.L.Chen, A. Hiraki, and J. Koolen, On distance-regular graphs with c4=1 and a1≧a2, Kyushu J. Math. 52 (1998) 265每277.

12. C.D. Godsil, Bounding the diameter of a distance-regular graph, Combinatorica 8 (1988) 333每343.

13. A. Hiraki, An improvement of the Boshier-Nomura bound, J. Combin. Theory Ser. B 61 (1994) 1每4.

14. A. Hiraki, A constant bound on the number of columns (1, k-2, 1) in the intersection array of distance-regular graphs, Graphs and Combin. 12 (1996) 23每37.

15. A. Hiraki, Distance-regular subgraph in a distance-regular graph, III, Europ. J. Combin. 17 (1996) 629每636.

16. A. Hiraki, Distance-regular subgraph in a distance-regular graph, V, Europ. J. Combin. 19 (1998) 141每150.

17. A. Hiraki, Distance-regular subgraph in a distance-regular graph, VI, Europ. J. Combin. 19 (1998) 953每965.

18. A. Hiraki and J.H. Koolen, An improvement of the Ivanov bound, Ann. Combin. 2 (1998) 131每135.

19. A. Hiraki and H. Suzuki, On distance-regular graphs with b1 = cd-1, Math. Japonica 37 (1992) 751每756.

20. H. Suzuki, On strongly closed subgraph of highly regular graphs, Europ. J. Combin. 16 (1995) 197每220.

21. P. Terwilliger, Eigenvalue multiplicities of highly symmetric graphs, Discrete Math. 41 (1982) 295每302.

22. R.R. Zhu, The distance-regular graphs with an eigenvalue of multiplicity four, J. Combin. Theory Ser. B 57 (1993) 157每182.