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

van Dam, Edwin R.; Haemers, Willem H.

Linear Algebra Appl. 373, 241-272 (2003).

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

Keywords:

spectra of graphs; eigenvalues; cospectral graphs; distance-regular graphs

References:

[1]	Berlekamp, E.R.; van Lint, J.H.; Seidel, J.J., A strongly regular graph derived from the perfect ternary golay code, (), 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, (), 667-685 · Zbl 0848.05071
[8]	Brouwer, A.E.; Cohen, A.M.; Neumaier, A., Distance-regular graphs, (1989), 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
[12]	F.C. Bussemaker, D.M. Cvetković, J.J. Seidel, Graphs related to exceptional root systems, T.H.-Report 76-WSK-05, Eindhoven University of Technology, 1976 · Zbl 0338.05116
[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, n1=12, n2=15, and p112=4, Sci. record, 4, 12-18, (1960)
[16]	F.R.K. Chung, Spectral Graph Theory, AMS, Providence, RI, 1994
[17]	Collatz, L.; Sinogowitz, U., Spektren endlicher grafen, Abh. math. sem. univ. Hamburg, 21, 63-77, (1957) · Zbl 0077.36704
[18]	K. Coolsaet, J. Degraer, A computer assisted proof of the uniqueness of the Perkel graph, Designs, Codes and Cryptography, in press · Zbl 1056.05149
[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
[21]	D.M. Cvetković, M. Doob, Root systems, forbidded subgraphs and spectral characterizations of line graphs, in: Cvetković, Gutman, Pisanski, Tošić (Eds.) Graph Theory, Proc. Fourth Yugoslav Sem. Graph Theory, Novi Sad, 1983, pp. 69-99
[22]	D.M. Cvetković, M. Doob, I. Gutman, A. Torgašev, Recent Results in the Theory of Graph Spectra, in: Annals of Discrete Mathematics, vol. 36, North-Holland, Amsterdam, 1988
[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
[24]	D.M. Cvetković, P. Rowlinson, S. Simić, Spectral generalizations of line graphs; a research monograph on graphs with least eigenvalue −2, manuscript
[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
[29]	E.R. van Dam, J.H. Koolen, private communication
[30]	van Dam, E.R.; Spence, E., Small regular graphs with four eigenvalues, Discrete math., 189, 233-257, (1998) · Zbl 0956.05070
[31]	E.R. van Dam, E. Spence, Combinatorial designs with two singular values I. Uniform multiplicative designs, in preparation · Zbl 1048.05017
[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
[39]	Godsil, C.D.; McKay, B.D., Some computational results on the spectra of graphs, (), 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
[45]	W.H. Haemers, E. Spence, Enumeration of cospectral graphs, European J. Combin., in press. Also: Center discussion paper 2002-90, Tilburg University · Zbl 1033.05070
[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
[53]	J.H. van Lint, J.J. Seidel, Equilateral point sets in elliptic geometry, Proc. Nederl. Akad. Wetenschappen A 69 (1966) 335-348 · Zbl 0138.41702
[54]	Lubotzky, A., Cayley graphs: eigenvalues, expanders and random walks, (), 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 London · Zbl 0551.05027
[59]	Rowlinson, P., The characteristic polynomials of modified graphs, Discrete appl. math., 67, 209-219, (1996) · Zbl 0851.05076
[60]	H. Sachs, Über Teiler, Faktoren und charakteristische Polynome von Graphen, Teil II, Wiss. Z. TH Ilmenau 13 (1967) 405-412 · Zbl 0162.27803
[61]	Schwenk, A.J., Almost all trees are cospectral, (), 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
[63]	J.J. Seidel, Graphs and two-graphs, in: F. Hoffman et al. (Eds.) Proc. 5th Southeast. Conf. Comb., Graph Th., Comp., Utilitas Mathematica Pub., Winnipeg, 1974, pp. 125-143 · Zbl 0308.05120
[64]	J.J. Seidel, A survey of two-graphs, in: Teorie Combinatorie (Proc. Intern. Coll., Roma 1973), Accad. Nac. Lincei, Roma, 1976, pp. 481-511
[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 L2 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) · JFM 58.0609.01