Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A Quasi-Spectral Characterization of Strongly Distance-Regular Graphs. | A Quasi-Spectral Characterization of Strongly Distance-Regular Graphs M. A. Fiol Departament de Matematica Aplicada i Telematica Universitat Politecnica de Catalunya Jordi Girona 1-3 Modul C3 Campus Nord 08034 Barcelona Spain email fiol@ Submitted April 30 2000 Accepted September 16 2000. Abstract A graph r with diameter d is strongly distance-regular if r is distanceregular and its distance-d graph 14 is strongly regular. The known examples are all the connected strongly regular graphs . d 2 all the antipodal distanceregular graphs and some distance-regular graphs with diameter d 3. The main result in this paper is a characterization of these graphs among regular graphs with d distinct eigenvalues in terms of the eigenvalues the sum of the multiplicities corresponding to the eigenvalues with non-zero even subindex and the harmonic mean of the degrees of the distance-d graph. AMS subject classifications. 05C50 05E30 1 Preliminaries Strongly distance-regular graphs were recently introduced by the author 9 by combining the standard concepts of distance-regularity and strong regularity. A strongly distance-regular graph r is a distance-regular graph of diameter d say with the property that the distance-d graph rd where two vertices are adjacent whenever they are at distance d in r is strongly regular. The only known examples of these graphs are the strongly regular graphs with diameter d 2 the antipodal distance-regular graphs and the distance-regular graphs with d 3 and third greatest eigenvalue X2 1. In fact it has been conjectured that a strongly distance-regular graph is antipodal or has diameter at most three. For these three families some spectral or quasi-spectral characterizations are known. Thus it is well-known that strongly regular graphs are characterized among regular connected graphs as those having THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R51 2 exactly three distinct eigenvalues. In the other two cases however the spectrum is not .
