Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The spectral excess theorem for distance-regular graphs: a global (over)view. | The spectral excess theorem for distance-regular graphs a global over view Edwin R. van Dam Tilburg University Dept. Econometrics O.R. PO Box 90153 5000 LE Tilburg The Netherlands Edwin.vanDam@uvt.nl Submitted April 24 2008 Accepted Oct 3 2008 Published Oct 13 2008 Mathematics Subject Classification 05E30 05B20 Keywords distance-regular graphs eigenvalues of graphs spectral excess theorem Abstract Distance-regularity of a graph is in general not determined by the spectrum of the graph. The spectral excess theorem states that a connected regular graph is distance-regular if for every vertex the number of vertices at extremal distance the excess equals some given expression in terms of the spectrum of the graph. This result was proved by Fiol and Garriga From local adjacency polynomials to locally pseudo-distance-regular graphs J. Combinatorial Th. B 71 1997 162-183 using a local approach. This approach has the advantage that more general results can be proven but the disadvantage that it is quite technical. The aim of the current paper is to give a less technical proof by taking a global approach. 1 Introduction It is known that distance-regularity of a graph is in general not determined by the spectrum of the graph cf. 7 and 11 for recent results on spectral characterizations of distance-regular graphs. By the spectral excess theorem we mean the remarkable result by Fiol and Garriga 13 that a connected regular graph with d 1 distinct eigenvalues is distance-regular if for every vertex the number of vertices at distance d from that vertex the excess equals a given expression in terms of the spectrum. So besides the spectrum a simple combinatorial property suffices for a graph to be distance-regular. The first result in this direction was obtained by Cvetkovic 2 and by Laskar 18 who showed that for a Hamming graph with diameter three and consequently a Doob graph with diameter three distance-regularity is determined by the spectrum and having the correct number of .
