×

Which graphs are determined by their spectrum? (English) Zbl 1026.05079

Summary: For almost all graphs the answer to the question in the title is still unknown. Here we survey the cases for which the answer is known. Not only the adjacency matrix, but also other types of matrices, such as the Laplacian matrix, are considered.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05E30 Association schemes, strongly regular graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berlekamp, E. R.; van Lint, J. H.; Seidel, J. J., A strongly regular graph derived from the perfect ternary Golay code, (Shrivastava, J. N., A Survey in Combinatorial Theory (1973), North-Holland: North-Holland Amsterdam), 25-30 · Zbl 0258.05129
[2] Biggs, N. L., Algebraic Graph Theory (1974), Cambridge University Press · Zbl 0501.05039
[3] Bose, R. C., Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math., 13, 389-419 (1963) · Zbl 0118.33903
[4] Botti, P.; Merris, R., Almost all trees share a complete set of immanantal polynomials, J. Graph Theory, 17, 467-476 (1993) · Zbl 0782.05038
[5] Brooks, R., Non-Sunada graphs, Ann. Inst. Fourier (Grenoble), 49, 707-725 (1999) · Zbl 0926.58021
[6] Brouwer, A. E., The uniqueness of the strongly regular graph on 77 points, J. Graph Theory, 7, 455-461 (1983) · Zbl 0523.05021
[7] Brouwer, A. E., Strongly regular graphs, (Colbourn, C. J.; Denitz, J. H., The CRC Handbook of Combinatorial Designs (1996), CRC Press), 667-685 · Zbl 0848.05071
[8] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Heidelberg · Zbl 0747.05073
[9] 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
[10] Brouwer, A. E.; Haemers, W. H., Structure and uniqueness of the (81,20,1,6) strongly regular graph, Discrete Math., 106/107, 77-82 (1992) · Zbl 0764.05098
[11] Brualdi, R. A.; Ryser, H. J., Combinatorial Matrix Theory (1991), Cambridge University Press · Zbl 0746.05002
[13] Cameron, P. J.; Goethals, J. M.; Seidel, J. J., Strongly regular graph having strongly regular subconstituents, J. Algebra, 55, 257-280 (1978) · Zbl 0444.05045
[14] Cameron, P. J.; Goethals, J. M.; Seidel, J. J.; Shult, E. E., Line graphs, root systems, and elliptic geometry, J. Algebra, 43, 305-327 (1976) · Zbl 0337.05142
[15] Chang, L. C., Association schemes of partially balanced block designs with parameters \(v=28, n_1=12, n_2=15\), and \(p_{11}^2=4\), Sci. Record, 4, 12-18 (1960) · Zbl 0093.32101
[17] Collatz, L.; Sinogowitz, U., Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 21, 63-77 (1957) · Zbl 0077.36704
[19] Cvetković, D. M., Graphs and their spectra, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 354-356, 1-50 (1971) · Zbl 0238.05102
[20] Cvetković, D. M., Constructing trees with given eigenvalues and angles, Linear Algebra Appl., 105, 1-8 (1988) · Zbl 0679.05053
[23] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs (1995), Johann Abrosius Barth Verlag, first edition: Deutscher Verlag der Wissenschaften, Berlin, 1980; Academic Press, New York, 1980 · Zbl 0824.05046
[25] van Dam, E. R., Regular graphs with four eigenvalues, Linear Algebra Appl., 226-228, 139-162 (1995) · Zbl 0839.05072
[26] van Dam, E. R., Nonregular graphs with three eigenvalues, J. Combin. Theory B, 73, 101-118 (1998) · Zbl 0917.05044
[27] van Dam, E. R.; Haemers, W. H., Graphs with constant \(μ\) and \(μ\), Discrete Math., 182, 293-307 (1998) · Zbl 0901.05068
[28] van Dam, E. R.; Haemers, W. H., Spectral characterizations of some distance-regular graphs, J. Algebra Combin., 15, 189-202 (2002) · Zbl 0993.05149
[30] van Dam, E. R.; Spence, E., Small regular graphs with four eigenvalues, Discrete Math., 189, 233-257 (1998) · Zbl 0956.05070
[32] Doob, D. M., Seidel switching and cospectral graphs with four distinct eigenvalues, Ann. New York Acad. Sci., 319, 164-168 (1979) · Zbl 0495.05046
[33] Doob, M.; Haemers, W. H., The complement of the path is determined by its spectrum, Linear Algebra Appl., 356, 57-65 (2002) · Zbl 1015.05047
[34] Fiol, M. A.; Garriga, E., From local adjacency polynomials to locally pseudo-distance-regular graphs, J. Combin. Theory B, 71, 162-183 (1997) · Zbl 0888.05056
[35] Fisher, M., On hearing the shape of a drum, J. Combin. Theory, 1, 105-125 (1966) · Zbl 0139.43302
[36] Fujii, H.; Katsuda, A., Isospectral graphs and isoperimetric constants, Discrete Math., 207, 33-52 (1999) · Zbl 1131.05309
[37] Gewitz, A., Graphs with maximal even girth, Canad. J. Math., 21, 915-934 (1969) · Zbl 0181.51801
[38] Godsil, C. D., Algebraic Combin. (1993), Chapman & Hall · Zbl 0784.05001
[39] Godsil, C. D.; McKay, B. D., Some computational results on the spectra of graphs, (Casse, L. R.A.; Wallis, W. D., Combinatorial Mathematics IV (Proceedings of the Fourth Australian Conference on Combinatorial Mathematics, Adelaide). Combinatorial Mathematics IV (Proceedings of the Fourth Australian Conference on Combinatorial Mathematics, Adelaide), Lecture Notes in Mathematics, vol. 560 (1976), Springer-Verlag: Springer-Verlag Berlin), 73-92 · Zbl 0534.05016
[40] Godsil, C. D.; McKay, B. D., Constructing cospectral graphs, Aequationes Math., 25, 257-268 (1982) · Zbl 0527.05051
[41] Goethals, J. M.; Seidel, J. J., The regular two-graph on 276 vertices, Discrete Math., 12, 143-158 (1975) · Zbl 0311.05121
[42] Günthard, Hs. H.; Primas, H., Zusammenhang von Graphentheorie und MO-Theorie von Molekeln mit Systemen konjugierter Bindungen, Helv. Chim. Acta, 39, 1645-1653 (1956)
[43] Haemers, W. H., Distance-regularity and the spectrum of graphs, Linear Algebra Appl., 236, 265-278 (1996) · Zbl 0845.05101
[44] Haemers, W. H.; Spence, E., Graphs cospectral with distance-regular graphs, Linear and Multilinear Algebra, 39, 91-107 (1995) · Zbl 0831.05045
[46] Halbeisen, L.; Hungerbühler, N., Generation of isospectral graphs, J. Graph Theory, 31, 255-265 (1999) · Zbl 0932.05053
[47] Halbeisen, L.; Hungerbühler, N., Reconstruction of weighted graphs by their spectrum, European J. Combin., 21, 641-650 (2000) · Zbl 0964.05046
[48] Hoffman, A. J., On the polynomial of a graph, Amer. Math. Monthly, 70, 30-36 (1963) · Zbl 0112.14901
[49] Huang, T.; Liu, C., Spectral characterization of some generalized odd graphs, Graphs Combin., 15, 195-209 (1999) · Zbl 0934.05088
[50] Johnson, C. R.; Newman, M., A note on cospectral graphs, J. Combin. Theory B, 28, 96-103 (1980) · Zbl 0431.05021
[51] Kac, M., Can one hear the shape of a drum?, Amer. Math. Monthly, 73, 1-23 (1966) · Zbl 0139.05603
[52] Lepović, M.; Gutman, I., No starlike trees are cospectral, Discrete Math., 242, 291-295 (2002) · Zbl 0992.05054
[54] Lubotzky, A., Cayley graphs: eigenvalues, expanders and random walks, (in: Surveys in Combinatorics, 1995 (Stirling). in: Surveys in Combinatorics, 1995 (Stirling), London Math. Soc. Lecture Note Ser., vol. 218 (1995), Cambridge University Press: Cambridge University Press Cambridge), 155-189 · Zbl 0835.05033
[55] McKay, B. D., On the spectral characterisation of trees, Ars Combin., 3, 219-232 (1979) · Zbl 0404.05045
[56] McKay, B. D.; Spence, E., Classification of regular two-graphs on 36 and 38 vertices, Austral. J. Combin., 24, 293-300 (2001) · Zbl 0979.05110
[57] Merris, R., Large families of Laplacian isospectral graphs, Linear and Multilinear Algebra, 43, 201-205 (1997) · Zbl 0887.05036
[58] Payne, S. E.; Thas, J. A., Finite Generalized Quadrangles (1984), Pitman: Pitman London · Zbl 0551.05027
[59] Rowlinson, P., The characteristic polynomials of modified graphs, Discrete Appl. Math., 67, 209-219 (1996) · Zbl 0851.05076
[61] Schwenk, A. J., Almost all trees are cospectral, (Harary, F., New Directions in the Theory of Graphs (1973), Academic Press: Academic Press New York), 275-307 · Zbl 0261.05102
[62] Seidel, J. J., Strongly regular graphs with (−1,1,0) adjacency matrix having eigenvalue 3, Linear Algebra Appl., 1, 198-281 (1968) · Zbl 0159.25403
[65] Seress, Á., Large families of cospectral graphs, Designs, Codes and Cryptography, 21, 205-208 (2000) · Zbl 0972.05033
[66] Shrikhande, S. S., The uniqueness of the \(L_2\) association scheme, Ann. Math. Statist., 30, 781-798 (1959) · Zbl 0086.34802
[67] Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-167 (1932)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.