×

zbMATH — the first resource for mathematics

Some spectral and quasi-spectral characterizations of distance-regular graphs. (English) Zbl 1342.05031
Summary: In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth.

MSC:
05C12 Distance in graphs
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Biggs, N., Algebraic graph theory, (1974), Cambridge University Press Cambridge, second edition, 1993 · Zbl 0284.05101
[2] Brouwer, A. E.; Haemers, W. H., The gewirtz graph: an exercise in the theory of graph spectra, European J. Combin., 14, 397-407, (1993) · Zbl 0794.05076
[3] Brouwer, A. E.; Haemers, W. H., Spectra of graphs, (2012), Springer, available online at: · Zbl 0794.05076
[4] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-regular graphs, (1989), Springer-Verlag Berlin-New York · Zbl 0747.05073
[5] Cámara, M.; Fàbrega, J.; Fiol, M. A.; Garriga, E., Some families of orthogonal polynomials of a discrete variable and their applications to graphs and codes, Electron. J. Combin., 16, 1, (2009) · Zbl 1230.05120
[6] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of graphs. theory and application, (1982), VEB Deutscher Verlag der Wissenschaften Berlin
[7] Dalfó, C.; van Dam, E. R.; Fiol, M. A.; Garriga, E.; Gorissen, B. L., On almost distance-regular graphs, J. Combin. Theory Ser. A, 118, 1094-1113, (2011) · Zbl 1225.05249
[8] van Dam, E. R., Three-class association schemes, J. Algebraic Combin., 10, 69-107, (1999) · Zbl 0929.05096
[9] van Dam, E. R., The spectral excess theorem for distance-regular graphs: a global (over)view, Electron. J. Combin., 15, 1, (2008) · Zbl 1180.05130
[10] van Dam, E. R.; Fiol, M. A., A short proof of the odd-girth theorem, Electron. J. Combin., 19, 3, 12, (2012)
[11] van Dam, E. R.; Haemers, W. H., Spectral characterizations of some distance-regular graphs, J. Algebraic Combin., 15, 189-202, (2002) · Zbl 0993.05149
[12] van Dam, E. R.; Haemers, W. H., Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272, (2003) · Zbl 1026.05079
[13] van Dam, E. R.; Haemers, W. H., Developments on spectral characterizations of graphs, Discrete Math., 309, 576-586, (2009) · Zbl 1205.05156
[14] van Dam, E. R.; Haemers, W. H., An odd characterization of the generalized odd graphs, J. Combin. Theory Ser. B, 101, 486-489, (2011) · Zbl 1234.05157
[15] van Dam, E. R.; Haemers, W. H.; Koolen, J. H.; Spence, E., Characterizing distance-regularity of graphs by the spectrum, J. Combin. Theory Ser. A, 113, 1805-1820, (2006) · Zbl 1105.05076
[16] van Dam, E. R.; Koolen, J. H.; Tanaka, H., Distance-regular graphs, Electron. J. Combin., (2016) · Zbl 1335.05062
[17] Fiol, M. A., Algebraic characterizations of distance-regular graphs, Discrete Math., 246, 111-129, (2002) · Zbl 1025.05060
[18] Fiol, M. A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory Ser. B, 71, 162-183, (1997) · Zbl 0888.05056
[19] Fiol, M. A.; Gago, S.; Garriga, E., A simple proof of the spectral excess theorem for distance-regular graphs, Linear Algebra Appl., 432, 2418-2422, (2010) · Zbl 1221.05112
[20] Godsil, C. D., Algebraic combinatorics, (1993), Chapman and Hall New York · Zbl 0814.05075
[21] Haemers, W. H., Distance-regularity and the spectrum of graphs, Linear Algebra Appl., 236, 236-278, (1996) · Zbl 0845.05101
[22] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36, (1963) · Zbl 0112.14901
[23] Huang, T.; Liu, C., Spectral characterization of some generalized odd graphs, Graphs Combin., 15, 195-209, (1999) · Zbl 0934.05088
[24] Lee, G.-S.; Weng, C.-W., The spectral excess theorem for general graphs, J. Combin. Theory Ser. A, 119, 1427-1431, (2012) · Zbl 1245.05087
[25] Perkel, M., Bounding the valency of polygonal graphs with odd girth, Canad. J. Math., 31, 1307-1321, (1979) · Zbl 0465.20002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.