Abstract
LetG be a connected distance-regular graph with valencyk>2 and diameterd, but not a complete multipartite graph. Suppose thatθ is an eigenvalue ofG with multiplicitym and thatθ≠±k. We prove that bothd andk are bounded by functions ofm. This implies that, ifm>1 is given, there are only finitely many connected, co-connected distance-regular graphs with an eigenvalue of multiplicitym.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
E. Bannai and T. Ito,Algebraic Combinatorics I, Benjamin/Cummings, 1984.
N. L. Biggs,Algebraic Graph Theory, Cambridge University Press, 1974.
N. L. Biggs, A. G. Boshier andJ. Shawe-Taylor, Cubic distance-regular graphs, J. London Math. Soc.,33 (1986), 385–394.
Ph. Delsarte, J. M. Goethals andJ. J. Seidel, Spherical codes and designs, Geom. Dedicata,6 (1977), 363–388.
C. D. Godsil, Graphs, groups and polytopes, in: Combinatorial Mathematics, (ededited by D. A. Holton and Jannifer Seberry) pp. 157–164, Lecture Notes in Mathematics 686, Springer, Berlin 1978.
P. Henrici, Applied and Computational Complex Analysis, Vol. 1, Wiley, New York, 1974.
D. L. Powers, Eigenvectors of distance-regular graphs,submitted.
D. E. Taylor andR. Levingston, Distance-regular graphs, in: Combinatorial Mathematics, (ededited by D. A. Holton and Jennifer Seberry) pp. 313–323, Lecture Notes in Mathematics 686, Springer, Berlin 1978.
P. Terwilliger, Eigenvalue multiplicities of highly symmetric graphs, Discrete Math.,41 (1982), 295–302.
P. Terwilliger, A new feasibility condition for distance-regular graphs, Discrete Math.,61 (1986), 311–315.
Author information
Authors and Affiliations
Additional information
This work was supported by NSERC grant A5367.
Rights and permissions
About this article
Cite this article
Godsil, C.D. Bounding the diameter of distance-regular graphs. Combinatorica 8, 333–343 (1988). https://doi.org/10.1007/BF02189090
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02189090