It is known that there exist many pairs of nonisomorphic graphs which have the same set of eigenvalues, even when counting multiplicities. Such graphs have identical characteristic polynomials (of their adjacency matrices) and are said to be cospectral.
Such a result remains true even when we restrict to some rather limited classes of graphs. For example, it is known that "almost all trees are cospectral". This last statement holds in a much stronger sense; namely, there are many nonisomorphic pairs of trees that have the same characteristic polynomial not only for the adjacency matrix but at the same time also for their Laplacian matrix and their distance matrix [1].
From another perspective, D. Cvetkovic and D. Stevanovic asked at the Glasgow Meeting on Algebraic Graph Theory in July 2001, if the fullerene graphs may be determined by their eigenvalues (characteristic polynomials) together with the collection of the angles between the standard basis and the eigenspaces (cf. [2]). Let us recall that fullerene graphs are 3-connected cubic planar graphs with 12 faces of size 5 and all other faces of size 6.
The result of Tutte on the "spring" embeddings of planar graphs [3] encouraged me to propose the following stronger conjectures:
Conjecture 1. Eigenvalues and angles determine cubic 3-connected planar graphs up to isomorphism.Conjecture 2. Eigenvalues and angles of the Laplacian matrix determine 3-connected planar graphs up to isomorphism.
[1] P. Botti, R. Merris, Almost all trees share a complete set of immanantal polynomials, J. Graph Theory 17 (1993) 467-476.
[2] D. Cvetkovic, P. Rowlinson, S. Simic, Eigenspaces of graphs, Encyclopedia of Mathematics and its Applications 66, Cambridge University Press, Cambridge, 1997.
[3] W. T. Tutte, How to draw a graph, Proc. London Math. Soc. 13 (1963) 743-768.
Send comments to Bojan.Mohar@uni-lj.si